TIN
Z Varhoo
(Rozdíly mezi verzemi)
(→Rekurzivně spočetný jazyk) |
(→Rekurzivně spočetný jazyk) |
||
| Řádka 41: | Řádka 41: | ||
Někdy taky zvané '''Jazyky rekurzívně vyčíslitelné a jazyky rekurzívní |
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=== |
===Jazyky mimo typ 0=== |
||
Verze z 20. 1. 2012, 17:30
Obsah |
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
