?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.