Gramatiky pro regulární jazyky
Tvrzení: Pro každou PLG G existuje KA M, pro který platí: L(G) = L(M).
Důkaz: Viz. str. 575 v knize [Meduna: Automata and Languages]
Závěr: Gramatiky pro regulární jazyky jsou
Pravé lineární gramatiky
Tvrzení: Pro každý KA M existuje PLG G, pro kterou platí: L(M) = L(G).
Důkaz: Viz. str. 583 v knize [Meduna: Automata and Languages]
35/45