Kontekstivabad grammatikad ja automaadid
Paremlineaarsed grammatikad ja lõplik automaat
- Veendume JFLAP abil, et iga regulaarne keel on kontekstivaba.
- Teeme JFLAP-is lahti järgmine automaat: cfg.jff.
- Valime menüüst "Convert" -> "Convert to Grammar".
- Konverteerime ka saadud grammatika tagasi automaadiks. Sellega loodetavasti selgub, kuidas igast paremlineaarsest grammatikast võib luua samaväärse automaadi. Seega, iga paremlineaarne grammatika spetsifitseerib regulaarse keele.
Kontekstivaba grammatika ja mägasinmäluga automaat
Igale kontekstivabale keelele vastab magasinmäluga automaat (PDA). Nende automaatide loomise kohta on võimalik informatsiooni leida siit. Alustame järgmise lihtsa grammatikaga (simple.jff):
S → aSb
S → ε
Loome koos sellele vastav automaat. Seejärel proovige ise luua järgmise grammatikale vastav automaat.
S → aSa
S → bSb
S → ε
Tegelikult saab süstemaatiliselt teisendada iga grammatika automaadiks. Selleks on kaks põhilist konstruktsiooni, üks mis vastab LL parseritele ja teine vastab LR parseritele. Võite proovida "Convert CFG to PDA(LL)", aga see on rohkem tuleviku teema.