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]