Rozhodnutelné jazyky
44/45
Myšlenka: Rozhodnutelné jazyky jsou přijímány TS, které vždy zastaví
Illustration:
Definice: Nechť L je jazyk. Pokud existuje DTS M, který vždy zastaví a pro který platí L = L(M), potom L je rozhodnutelný jazyk.
Tvrzení: Třída rozhodnutelných jazyků je uzavřena vůči doplňku.
Důkaz: Viz. str. 693 v knize [Meduna: Automata and Languages]
Tvrzení: Třída rekurzivně vyčíslitelných jazyků není uzavřena vůči doplňku.
Důkaz: Viz. jazyk LPřijmeSámSebe