INF1800 H?sten 2007

Obligatorisk oppgave 4 Innleveringsfrist 16. november

Spr”ćaket av strenger fra alfabetet {a, b} som inneholder mindre enn to forekomster av b kan vi kalle
L<2. Det beskrives av det regul?re uttrykket a(b + )a.

Del 1 Besvar f?lgende oppgaver ved hjelp av algoritmene beskrevet i boken, eller bruk JFLAP:

1. Finn en NFA for L<2.
2. Finn en DFA for L<2.
3. Finn en minimal DFA for L<2.
4. Komplementet til L<2 er spr”ćaket av strenger fra alfabetet {a, b} som inneholder minst to
forekomster av b. Vi kan kalle det L2. Finn en DFA for L2.
5. Finn et regul?rt uttrykk for L2.

Del 2 Ta utgangspunkt i automatene du fant i del 1, og finn DFA”Æer for spr”ćakene L<3 og L=2 av
strenger over alfabetet {a, b} med henholdsvis mindre enn 3, og n?yaktig 2, forekomster av b. Finn
deretter h?yreline?re grammatikker for disse spr”ćakene.

Del 3 Skriv en kontekstfri grammatikk for spr”ćaket av strenger over alfabetet {a, b, c} med n?yaktig
en forekomst av c og med like mange forekomster av b f?r og etter c, og uten restriksjoner p”ća
forekomster av a. Eksempler p”ća strenger i dette spr”ćaket er alts”ća caaaa, aaaaabaaacb, ababacaaaabb,
og s”ća videre.