Modely
pro bezkontextové jazyky
Důkaz
je založen na předchozím
algoritmu
Tvrzení: Pro každou BKG G
existuje ZA M, pro
který platí: L(G) = L(M)e.
Důkaz: Viz. str. 486 v knize [Meduna: Automata and Languages]
Tvrzení: Pro každý ZA M existuje
BKG G, pro
kterou platí: L(M)e = L(G).
Závěr: Fundamentální
modely pro bezkontextové jazyky jsou:
1) Bezkontextové gramatiky
2)
Zásobníkové
automaty
50/50