Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky

Základní pojmy

Abeceda Σ

Neprázdná konečná množina, jejíž prvky nazýváme symboly.

Řetezec / slovo / věta w

Konečná posloupnost symbolů abecedy.

Alternativní definice:

Prázdný řetezec je řetezec.

Je-li w řetězec a a symbol abecedy pak wa je řetezec.

Řetězce jsou vše, co lze získat jen a pouze aplikací předchozích pravidel

Prázdný řetezec ε

Řetezec neobsahující žádný symbol

Konkatenace xy (někdy x.y)

Připojení řetezce za jiný řetezec

Konkatenace je asociativní

Prázdný řetezec je neutrální prvek vzhledem ke konkatenaci

Iterace Σ*

Množina všech řetězců nad abecedou Σ.

Volný monoid nad abecedou Σ generovaný operací konkatenace.

Pozitivní iterace Σ⁺

Iterace bez prázdného řetezce

Formální jazyk L

Jakákoli podmnožina L ⊆ Σ*.

Konkatenace jazyků

Rozumíme binární operaci L₁ . L₂ = {xy | x ∈ L₁ ∧ y ∈ L₂}

Iterace jazyka

L⁰ = {ε}

Lⁿ = L . Lⁿ⁻¹, n ≥ 1

L* = ∪ Lⁿ, n ≥ 0

L⁺ = ∪ Lⁿ, n ≥ 1

Gramatika

Gramatika G = (N, Σ, P, S)

N – konečná množina nonterminálních symbolů (nonterminálů)

Σ – konečná množina terminálních symbolů (terminálů)

P – je konečná množina přepisovacích pravidel

S – počáteční nonterminál S ∈ N

Přepisovací pravidlo

Podmnožina kartézského součinu (N ∪ Σ)*N(N ∪ Σ)* × (N ∪ Σ)*

(a, b) ∈ P zapisujeme ve tvaru a → b, kde a je levá strana a b je pravá strana pravidla.

Přímá derivace ⇒

Binární relace mezi řetezci u a v která platí pokud můžeme řetezce zapsat jako u = gad, v = gbd a (a, b) ∈ P, tj. pokud lze řetězec v vytvořit z retězce u aplikací jednoho přepisovacího pravidla.

Derivace ⇒⁺

Tranzitivní uzávěr relace přímé derivace, tj. pokud lze vytvořit řetězec v z řetězce u postupnou aplikací několika přepisovacích pravidel.

Derivace ⇒*

Tranzitivní a reflexivní uzávěr relace přímé derivace, tj. pokud lze vytvořit řetězec v z řeťazca u postupnou aplikací několika přepisovacích pravidel nebo pokud jsou řetězce stejné.

Větná forma

Řetězec terminálů a nonterminálů, které jsou derivací počátečního nontermínálu

Věta

Větná forma obsahující pouze terminály

Jazyk generovaný gramatikou

Množina všech vět, které patří do gramatiky L(G) = {w | S ⇒* w ∧ w ∈ Σ*}

Chomského hierarchie klasifikace gramatik

Klasifikace je definována podle tvaru přepisovacích pravidel příslušných gramatik

Platí: L₃ ⊂ L₂ ⊂ L₁ ⊂ L₀

Dál neopraveno

Typ 0 – obecné (neomezené) gramatiky

Rekurzivně vyčíslitelné jazyky

Turingovy stroje

Tvar pravidel: α → β

α ∈ (N ∪ Σ)<sup>*</*sup>N(N ∪ Σ)<sup>*</*sup>

β ∈ (N ∪ Σ)<sup>*</*sup>

Typ 1 – kontextové gramatiky

* Jazyky: 'kontextové jazyky' * Automaty: 'lineárně omezené Turingovy stroje' * Tvar pravidel: :<math>\alpha A \beta \rightarrow \alpha \gamma \beta</math> (nebo <math>S \rightarrow \epsilon</math> pokud <math>\epsilon \in L</math> a <math>S</math> se nevyskytuje na pravé straně žádného pravidla.) :: <math>A \in N</math> :: <math>\alpha , \beta \in (N \cup \Sigma)^*</math> :: <math>\gamma \in (N \cup \Sigma)^+</math> * Nesmí dojít ke zkrácení větné formy.

Typ 2 – bezkontextové gramatiky

* Jazyky: 'bezkontextové jazyky' * Automaty: 'zásobníkové automaty' * Tvar pravidel: :<math>A \rightarrow \gamma</math> :: <math>A \in N</math> :: <math>\gamma \in (N \cup \Sigma)^*</math>

Typ 3 – pravé/levé linární gramatiky

* Jazyky: 'regulární jazyky' * Automaty: 'konečné automaty' * Tvar pravidel: :Pravá lineární: <math>A \rightarrow x B</math> nebo <math>A \rightarrow x</math> :Levá lineární: <math>A \rightarrow B x</math> nebo <math>A \rightarrow x</math> :: <math>A, B \in N</math> :: <math>x \in \Sigma^*</math>

Speciální podtypy gramatik

Pravé/levé regulární gramatiky

* ekvivalentní gramatikám typu 3 * Tvar pravidel: :Pravá regulární: <math>A \rightarrow a B</math> nebo <math>A \rightarrow a</math> :Levá regulární: <math>A \rightarrow B a</math> nebo <math>A \rightarrow a</math> :: <math>A, B \in N</math> :: <math>a \in \Sigma</math>

Lineární gramatiky

* podmnožina gramatik typu 2 * Tvar pravidel: : <math>A \rightarrow x B y</math> nebo <math>A \rightarrow x</math> :: <math>A, B \in N</math> :: <math>x, y \in \Sigma^*</math>

Deterministické bezkontextové gramatiky

* podmnožina typu 2 * jazyky příjamné deterministickým zásobníkovým automatem

Rekurzivní gramatiky

* podmnožina typu 0 * přijímají je 'úplné TS' (TS, které pro každý vstup rozhodnou - nikdy necyklí) * všechny kontextové jazyk jsou rekurzivní, ale ne všechny rekurzivní jazyky jsou kontextové