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

• Abeceda Σ
  • Neprázdná množina, jejíž prvky nazýváme symboly.
• Řetezec / slovo / věta w
  • Konečná posloupnost symbolů abecedy.
  • Alternativní definice:
    1. Prázdný řetezec je řetezec.
    2. Je-li w řetězec a a symbol abecedy pak wa je řetezec.
    3. Ř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 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 ∈ Σ^*}

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

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

Unrestricted grammar

• Rekurzivně vyčíslitelné jazyky
• Turingovy stroje
• Tvar pravidel: α → β
  • α ∈ (N ∪ Σ)^*N(N ∪ Σ)^*
  • β ∈ (N ∪ Σ)^*

Context-sensitive grammar

• 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

Context-free grammar

• Bezkontextové jazyky
• Zásobníkové automaty
• A → γ
  • A ∈ N
  • γ ∈ (N ∪ Σ)^*

Regular grammar

• 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 ∈ Σ^*

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

Podmnožina gramatik typu 2

• A → xBy nebo A → x
  • A, B ∈ N
  • x, y ∈ Σ^*

Podmnožina typu 2, jazyky příjamné deterministickým zásobníkovým automatem.

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