====== 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 //Σ//<sup>*</sup>**
    * 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// ⊆ //Σ//<sup>*</sup>.
  * **Konkatenace jazyků**
    * Rozumíme binární operaci //L//₁ . //L//₂ = {//xy// | //x// ∈ //L//₁ ∧ //y// ∈ //L//₂}
  * **Iterace jazyka**
    * //L//⁰ = {//ε//}
    * //Lⁿ// = //L// . //Lⁿ//⁻¹, //n// ≥ 1
    * //L//<sup>*</sup> = ∪ //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// ∪ //Σ//)<sup>*</sup>//N//(//N// ∪ //Σ//)<sup>*</sup> × (//N// ∪ //Σ//)<sup>*</sup>
    * (//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 =><sup>*</sup>**
    * 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// =><sup>*</sup> //w// ∧ //w// ∈ //Σ//<sup>*</sup>}

===== 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 ====
[[wp>Unrestricted grammar]]

  * Rekurzivně vyčíslitelné jazyky
  * Turingovy stroje
  * Tvar pravidel: //α// -> //β//
    * //α// ∈ (//N// ∪ //Σ//)<sup>*</sup>//N//(//N// ∪ //Σ//)<sup>*</sup>
    * //β// ∈ (//N// ∪ //Σ//)<sup>*</sup>
==== Typ 1 – kontextové gramatiky ====
[[wp>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// ∪ //Σ//)<sup>*</sup>
    * //γ// ∈ (//N// ∪ //Σ//)⁺
    * Nesmí dojít ke zkrácení větné formy
==== Typ 2 – bezkontextové gramatiky ====
[[wp>Context-free grammar]]

  * Bezkontextové jazyky
  * Zásobníkové automaty
  * //A// -> //γ//
    * //A// ∈ //N//
    * //γ// ∈ (//N// ∪ //Σ//)<sup>*</sup>
==== Typ 3 – pravé/levé linární gramatiky ====
[[wp>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// ∈ Σ<sup>*</sup>
==== Speciální podtypy gramatik ====
=== Pravé/levé regulární gramatiky ===
Stejné jako 3, ale //x// ∈ //Σ// (bez <sup>*</sup>).

=== Lineární gramatiky ===
Podmnožina gramatik typu 2

  * //A// -> //xBy// nebo //A// -> //x//
    * //A//, //B// ∈ //N//
    * //x//, //y// ∈ //Σ//<sup>*</sup>

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