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.