Rekurzivně vyčíslitelné jazyky
Tvrzení: Pro každou NG G existuje TS M, pro který platí: L(G) = L(M).
Důkaz: Viz. str. 714 v knize [Meduna: Automata and Languages]
Závěr: Fundamentální modely pro rekurzivně vyčíslitelné jazyky jsou:
1) Neomezené gramatiky
2) Turingovy stroje
Definice: Nechť L je jazyk. L je rekurzivně vyčíslitelný jazyk, pokud existuje Turingův stroj M takový, pro který platí: L = L(M).
Tvrzení: Pro každý TS M, existuje NG G, pro kterou platí: L(M) = L(G).
29/45
Důkaz: Viz. str. 715 v knize [Meduna: Automata and Languages]