TIN

Regulární jazyky

Uzávěrové vlastnosti regulárních jazyků:

• Sjednocení
• Průnik
• Konkatenace
• Komplement
• Substituce
• Morfismus
• Iterace
• Pozitivní iterace
• Rozdíl
• Zrcadlení

Rozhodnutelné problémy:

• Příslušnost jazyka
• Prázdnost
• Ekvivalence
• Inkluze
• Universita
• Konečnost

Bezkontextové jazyky

a k jazyku patřičná gramatika: context-free grammar (CFG)

Uzávěrové vlastnosti bezkontextové jazyky

• Sjednocení
• Konkatenace
• Substituce
• Morfismus
• Iteraci
• Pozitivní iteraci
• Zrcadlení

Kontextové jazyky

k jazyk generuje kontextová gramatika context-sensitive grammar (CSG)

Rekurzivně spočetný jazyk

Někdy taky zvané Jazyky rekurzívně vyčíslitelné a jazyky rekurzívní

• jazyky rekurzívně vyčíslitelné - zastaví pouze pro řětězec jazyku, který je schopen příjmout $$ w \in L$$
• jazyky rekurzívní - pro úplný Turingův stroj (pro každý vstup se zastaví)

Jazyky mimo typ 0

Mezi tyto jazyky patří například co-HP, co-MP

• Problém zastavení (halt problem)
• Problém náležitosti (membership problem)
• Postův korespondenční problém
• SAT problem