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