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