Øvelser til uke 46

I oppgave 1 side 700 og og oppgave 1 og 3 side 715 skal man ifølge oppgaveteksten skrive grammatikker eller stakkautomater for diverse språk.  Her endrer vi oppgavene slik at du skal skrive både en grammatikk og en stakkautomat for hvert språk. Lag dem så enkle du kan (og la PDA'er helst være deterministiske hvis du ser at det er mulig) og test dem ut i JFLAP.  Bruk deretter JFLAP til å finne en tilsvarende stakkautomat for hver grammatikk du har laget, og sammenlign med dine egne løsninger.

Kommentar:  JFLAPs "Convert to PDA(LL)" svarer nokså direkte til grammatikk-til-PDA-algoritmen i boken.  Den gir imidlertid ut en litt "liberal" type PDA som tillater pushing av flere stakksymboler i en og samme transisjon.  JFLAP har også en innebygget PDA-til-grammatikk-omformer som svarer til den som ble skisserte på forelesningen 7/11.  Her er  JFLAP imidlertid strengere mht. formatet, og aksepterer IKKE PDA'er som den selv har laget fra grammatikker.  En liten (stor?) ekstraoppgave her kan være å ta utgangspunkt i en PDA JFLAP har laget fra en grammatikk, og omforme den slik at hver transisjon har en av stakkoperasjonene pop (ett element), nop, eller push (ett element).  Løsning på denne oppgaven vil normalt kreve at man innfører ekstratilstander som vil fungere som mellomstasjoner for lengre stier av transisjoner som tilsvarer de opprinnelige transisjonene.

Gjør til slutt oppgave 1 side 755 i læreboken.