TIN

Z Varhoo
(Rozdíly mezi verzemi)
Přejít na: navigace, hledání
(→‎Regulární jazyky)
 
(Není zobrazeno 16 mezilehlých verzí od 1 uživatele.)
Řá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
   
 
Rozhodnutelné problémy:
  
Rozhodnutelné problémy:
Řádka 19: Řádka 19:
 
* Universita
  
* Universita
 
* Konečnost
  
* Konečnost
  +
  +
==Tabulka uzavřenosti==
  +
{| class="wikitable"
  +
|+ align="top"|Closure properties of language families (<math>L_1</math> Op <math>L_2</math> where both <math>L_1</math> and <math>L_2</math> are in the language family given by the column). After Hopcroft and Ullman.
  +
|-
  +
! Operation
  +
!
  +
! Regular
  +
! [[Deterministic context-free language|DCFL]]
  +
! [[Context free language|CFL]]
  +
! [[Indexed language|IND]]
  +
! [[Context sensitive language|CSL]]
  +
! [[Recursive language|recursive]]
  +
! [[Recursively enumerable language|RE]]
  +
|-
  +
|[[Union (set theory)|Union]]
  +
| <math>\{w | w \in L_1 \lor w \in L_2\} </math>
  +
| Yes
  +
| No
  +
| Yes
  +
| Yes
  +
| Yes
  +
| Yes
  +
| Yes
  +
|-
  +
|[[Intersection (set theory)|Intersection]]
  +
| <math>\{w | w \in L_1 \land w \in L_2\}</math>
  +
| Yes
  +
| No
  +
| No
  +
| No
  +
| Yes
  +
| Yes
  +
| Yes
  +
|-
  +
|[[Complement (set theory)|Complement]]
  +
| <math>\{w | w \not\in L_1\}</math>
  +
| Yes
  +
| Yes
  +
| No
  +
| No
  +
| Yes
  +
| Yes
  +
| No
  +
|-
  +
|[[Concatenation]]
  +
| <math>L_1\cdot L_2 = \{w\cdot z | w \in L_1 \land z \in L_2\}</math>
  +
| Yes
  +
| No
  +
| Yes
  +
| Yes
  +
| Yes
  +
| Yes
  +
| Yes
  +
|-
  +
|Kleene star
  +
| <math>L_1^{*} = \{\epsilon\} \cup \{w \cdot z | 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
  +
| <math>\{w^R | w \in L\} </math>
  +
| Yes
  +
| No
  +
| Yes
  +
| Yes
  +
| Yes
  +
| Yes
  +
| Yes
  +
|-
  +
|Intersection with a [[regular language]]
  +
| <math>\{w | w \in L_1 \land w \in R\}, R \text{ regular}</math>
  +
| Yes
  +
| Yes
  +
| Yes
  +
| Yes
  +
| Yes
  +
| Yes
  +
| Yes
  +
<!--
  +
|-
  +
|Min
  +
|
  +
| Yes
  +
| Yes
  +
| No
  +
| ???
  +
| Yes
  +
| Yes
  +
| Yes
  +
|-
  +
|Max
  +
|
  +
| Yes
  +
| Yes
  +
| No
  +
| ???
  +
| No
  +
| No
  +
| No
  +
|-
  +
|Init
  +
|
  +
| Yes
  +
| No
  +
| Yes
  +
| ???
  +
| No
  +
| No
  +
| Yes
  +
|-
  +
|Cycle
  +
|
  +
| Yes
  +
| No
  +
| Yes
  +
| ???
  +
| Yes
  +
| Yes
  +
| Yes
  +
|-
  +
|Shuffle
  +
|
  +
| Yes
  +
| ???
  +
| Yes
  +
| ???
  +
| ???
  +
| ???
  +
| Yes
  +
|-
  +
|Perfect Shuffle
  +
|
  +
| 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

Aktuální verze z 29. 1. 2012, 02: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

Closure properties of language families (<math>L_1</math> Op <math>L_2</math> where both <math>L_1</math> and <math>L_2</math> are in the language family given by the column). After Hopcroft and Ullman.
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
Citováno z „http://wiki.varhoo.cz/index.php?title=TIN&oldid=2584“
Osobní nástroje