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:
- Kõigepealt mõtleme, kuidas keele ära tundmine võiks toimida. Idee on lihtne: kasutame magasini, et loendada 'a'-sid ehk iga 'a' korral toppime midagi magasini ja siis hakkame iga 'b' korral elemente magasinist välja võtma.
- Joonista seisund, mis esitab seda, et hakkame 'a'-sid loendama. Tal on seega endale üleminek.
- Kui näeme 'b'-d, siis lähme järgmise seisundisse, kus hakkame elemente magasinist välja võtma.
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.