TIN
Z Varhoo
Obsah |
Regulární jazyky
Uzávěrové vlastnosti regulárních jazyků:
- Sjednocení - plyne z definice regulárních množin a ekvivalence regulárních jazyků
- Průnik - plyne z komplementu a de Morganových zákonů
- Konkatenace - plyne z definice regulárních množin a ekvivalence regulárních jazyků
- Komplement - plyne z toho že RJ vytváří Booleovu algebru
- Substituce
- Morfismus
- Iterace - plyne z definice regulárních množin a ekvivalence regulárních jazyků
- Pozitivní iterace
- Zrcadlení - Sesrtojení KA aby L(M) = L^r
Rozhodnutelné problémy:
- Příslušnost jazyka
- Prázdnost
- Ekvivalence
- Inkluze
- Universita
- Konečnost
Tabulka uzavřenosti
Operation | Regular | DCFL | CFL | IND | CSL | recursive | RE | |
---|---|---|---|---|---|---|---|---|
Union | w \in L_1 \lor w \in L_2\} </math> | Yes | No | Yes | Yes | Yes | Yes | Yes |
Intersection | w \in L_1 \land w \in L_2\}</math> | Yes | No | No | No | Yes | Yes | Yes |
Complement | w \not\in L_1\}</math> | Yes | Yes | No | No | Yes | Yes | No |
Concatenation | w \in L_1 \land z \in L_2\}</math> | Yes | No | Yes | Yes | Yes | Yes | Yes |
Kleene star | w \in L_1 \land z \in L_1^{*}\}</math> | Yes | No | Yes | Yes | Yes | Yes | Yes |
Homomorphism | Yes | No | Yes | Yes | No | No | Yes | |
e-free Homomorphism | Yes | No | Yes | Yes | Yes | Yes | Yes | |
Substitution | Yes | No | Yes | Yes | Yes | No | Yes | |
Inverse Homomorphism | Yes | Yes | Yes | Yes | Yes | Yes | Yes | |
Reverse | w \in L\} </math> | Yes | No | Yes | Yes | Yes | Yes | Yes |
Intersection with a regular language | w \in L_1 \land w \in R\}, R \text{ regular}</math> | Yes | Yes | Yes | Yes | Yes | Yes | Yes |
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