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

Základní pojmy

Abeceda Σ

Neprázdná 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₀

Typ 0 – obecné (neomezené) gramatiky

Rekurzivně vyčíslitelné jazyky

Turingovy stroje

Tvar pravidel: α → β

α ∈ (N ∪ Σ)*N(N ∪ Σ)*

β ∈ (N ∪ Σ)*

Typ 1 – kontextové gramatiky

Kontextové jazyky

Lineárně omezené Turingovy stroje

αAβ → αγβ, nebo S → ε pokud ε ∈ L a S se nevyskytuje na pravé straně žádného pravidla

A ∈ N

α, β ∈ (N ∪ Σ)*

γ ∈ (N ∪ Σ)⁺

Nesmí dojít ke zkrácení větné formy

Typ 2 – bezkontextové gramatiky

Bezkontextové jazyky

Zásobníkové automaty

A → γ

A ∈ N

γ ∈ (N ∪ Σ)*

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

Regulární jazyky

Konečné automaty

Pravá lineární: A → xB nebo A → x

Levá lineární: A → Bx nebo A → x

A, B ∈ N

x ∈ Σ*

Speciální podtypy gramatik

Pravé/levé regulární gramatiky

Stejné jako 3, ale x ∈ Σ (bez *).

Lineární gramatiky

Podmnožina gramatik typu 2

A → xBy nebo A → x

A, B ∈ N

x, y ∈ Σ*

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é.