• 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:
    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₀

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

• 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

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

* 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>

* 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>

* 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>

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