TIN
Z Varhoo
(Rozdíly mezi verzemi)
(→Jazyky mimo typ 0) |
|||
| Řádka 39: | Řádka 39: | ||
===Jazyky mimo typ 0=== |
===Jazyky mimo typ 0=== |
||
Mezi tyto jazyky patří například co-HP, co-MP |
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 |
||
Verze z 20. 1. 2012, 16:59
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
Uzávěrové vlastnosti bezkontextové jazyky
- Sjednocení
- Konkatenace
- Substituce
- Morfismus
- Iteraci
- Pozitivní iteraci
- Zrcadlení
Kontextové jazyky
Rekurzivně spočetný
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
