TIN
Z Varhoo
(Rozdíly mezi verzemi)
(→Regulární jazyky) |
(→Regulární jazyky) |
||
| Řádka 2: | Řádka 2: | ||
Uzávěrové vlastnosti regulárních jazyků: |
Uzávěrové vlastnosti regulárních jazyků: |
||
| − | * Sjednocení |
+ | * Sjednocení - plyne z definice regulárních množin a ekvivalence regulárních jazyků |
| − | * Průnik |
+ | * Průnik - plyne z komplementu a de Morganových zákonů |
| − | * Konkatenace |
+ | * Konkatenace - plyne z definice regulárních množin a ekvivalence regulárních jazyků |
| − | * Komplement |
+ | * Komplement - plyne z toho že RJ vytváří Booleovu algebru |
* Substituce |
* Substituce |
||
* Morfismus |
* Morfismus |
||
| − | * Iterace |
+ | * Iterace - plyne z definice regulárních množin a ekvivalence regulárních jazyků |
* Pozitivní iterace |
* Pozitivní iterace |
||
| − | * Rozdíl |
+ | * Zrcadlení - Sesrtojení KA aby L(M) = L^r |
| − | * Zrcadlení |
||
Rozhodnutelné problémy: |
Rozhodnutelné problémy: |
||
Aktuální verze z 29. 1. 2012, 01:17
Obsah |
[editovat] 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
[editovat] 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 |
[editovat] 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í
[editovat] Kontextové jazyky
k jazyk generuje kontextová gramatika context-sensitive grammar (CSG)
[editovat] 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í)
[editovat] 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
