Gramatika (N, Σ, P, S)

• Derivační strom
  • Uzly jsou prvky z N ∪ Σ
  • Kořen stromu je S
  • Uzly označené prvky z Σ jsou koncové uzly stromu
  • Hrany odpovídají přepisovacím pravidlům gramatiky P
  • Označení koncových uzlů zleva doprava tvoří větnou formu
  • Každé derivaci přísluší jeden derivační strom, ale jednomu stromu může příslušet více derivací (více způsobů jak sestavit stejný strom).
• Levá/pravá derivace
  • Při sestavování je vždy přepsán nejlevější/nejpravější nonterminál
• Fráze větné formy
  • Řada symbolů na koncových uzlech některého podstromu derivačního stromu (řada symbolů, které lze získat derivacemi z jednoho nonterminálu)
  • β je frází větné formy pokud S ⇒^* αAγ ∧ A ⇒⁺ β
• Jednoduchá fráze větné formy
  • Řada sybmolů na koncových uzlech jednopatrového podstormu derivačního stromu
  • β je jednoduchou frází větné formy pokud S ⇒^* αAγ ∧ A ⇒ β
• Nejlevější jednoduchá fráze (l-fráze)
  • Fráze větné formy, která se nachází nejvíce vlevo
• Víceznačnost
  • Věta je víceznačná pokud existuje více derivačních stromů tvořících tuto větu
  • Existují jazyky, které nelze generovat bez víceznačnosti
  • Gramatika, která obsahuje cykly je vždy víceznačná
• ε-pravidlo
  • A → ε (přepisují nonterminál na prázdný řetezec)
• A-pravidla
  • Všechna pravidla, která mají A na levé straně
• Jednoduchá pravidlo
  • A → B (přepisují nonterminál na jiný nonterminál)
• Zbytečné symboly
  • Nedostupné symboly (nelze jich dosáhnout žádným přepisem) a symboly negenerující terminální řetězce (nikdy nevytvoří větnou formu)
• Cyklus
  • A →⁺ A

• Vlastní gramatika
  • Gramatika bez zbytečných symbolů, bez cyklů a bez ε-pravidel
• Rekurzivní pravidla
  • Rekurzivní zleva: A → Aα
  • Rekurzivní zprava: A → αA
  • Rekurzivní: A → αAβ
  • Každý bezkontextový jazyk lze generovat gramatikou bez levé rekurze
  • Všechna pravidla s levou rekurzí lze nahradit pravidly s pravou rekurzí

Úkol z TINu 2010, Úkol z TINu 2011

Převod gramatiky (N, Σ, P, S) na gramatiku bez nedostupných stavů (N′, Σ′, P′, S)

1. Najdeme všechny dostupné terminály a nonterminály
   1. i = 0
   2. V₀ = {S} (tj. v nultém kroku je dostupný pouze počáteční stav)
   3. repeat
      1. Vᵢ₊₁ = Vᵢ ∪ {X | A → αXβ ∈ P ∧ A ∈ Vᵢ} (tj. do množiny dostupných přidáme všechny terminály a nonterminály, kterlé lze získat přepisem z některého nonterminálu z množiny dostupných z předchozího kroku)
      2. i++ (tj. přejdeme k dalšímu kroku)
   4. until Vᵢ₊₁ = Vᵢ₋₁ (tj. končíme pokud se nám v posledním kroku množina dostupných nezměnila)
2. Novou gramatiku sestavíme jako:
   • N′ = Vᵢ ∩ N (tj. použijeme pouze dosažitelené nonterminály)
   • Σ′ = Vᵢ ∩ Σ (tj. použijeme pouze dosažitelené terminály)
   • P′ ⊂ P obsahuje pouze pravidla používající pouze symboly z Vᵢ

Převod gramatiky (N, Σ, P, S) na gramatiku bez nedostupných stavů (N′, Σ, P′, S)

1. Nalezení nonterminálů, které produkují terminální řetězce
   1. i = 0
   2. N₀ = ∅ (tj. v nultém kroku začínáme s prázdnou množinou nonterminálů generujících terminální řetězce)
   3. repeat
      1. Nᵢ₊₁ = Nᵢ ∪ {A | A → α ∈ P ∧ α ∈ (Nᵢ ∪ Σ)^*} (tj. do množiny všechny terminály, které lze přepsat na řetězce skladádající se pouze z terminálů nebo nonterminálů, které jsou již v množině nonterminálů generujících terminální řetězce)
      2. i++ (tj. přejdeme k dalšímu kroku)
   4. until Nᵢ₊₁ = Nᵢ₋₁ (tj. končíme pokud se nám v posledním kroku množina nezměnila)
2. Vytvoříme gramatiku bez nonterminálů, které neprodukují terminální řetězce:
   • N′ = Nᵢ
   • P′ ⊂ P obsahuje pouze pravidla používající pouze symboly z Nᵢ
3. Odstraníme nedostupné symboly z gramatiky

Převod gramatiky (N, Σ, P, S) na gramatiku bez ε-pravidel (N′, Σ′, P′, S′)

1. Sestavení množiny nonterminálů, které mohou generovat ε N_ε
   • Postup je obdobný jako krok 1 algoritmu odstranění zbytečných symbolů pouze Nᵢ₊₁ = Nᵢ ∪ {A | A → α ∈ P ∧ α ∈ (Nᵢ ∪ {ε})^*}, N_ε = Nᵢ
2. Sestavíme novou množinu přepisovacích pravidel P′
   • Jestliže A → α₀B₁α₁…Bₖαₖ ∈ P, k ≥ 0 a všechna Bᵢ jsou v N_ε a žádný symbol αᵢ není v N_ε pak k P′ přidej všechny prvidla tvaru A → α₀X₁α₂X₂…Xₖαₖ kde Xᵢ je buď Bᵢ nebo ε. Nepřidává se pravidlo A → ε.
   • Tj. od každého pravidla sestavíme všechny možné kombinace, kde jsou jednotlivé částí přepsatelné na ε vynechány
3. Zavedeme nový počáteční nonterminál S′
4. Jestliže je S v N_ε pak přidáme do P′ pravidla S′ → ε a S′ → S

Převod gramatiky bez ε-pravidel (N, Σ, P, S) na gramatiku bez jednoduchých pravidel (N, Σ, P′, S)

1. Pro každé A ∈ N sestrojíme množinu N_A = {B | A ⇒^* B}
   1. i = 0
   2. N₀ = {A}
   3. repeat
      1. Nᵢ₊₁ = Nᵢ ∪ {C | B → C ∈ P ∧ B ∈ Nᵢ}
      2. i++
   4. until Nᵢ = Nᵢ₋₁ (tj. končíme pokud se nám v posledním kroku množina nezměnila)
   5. N_A = Nᵢ
2. Sestavíme novou množinu P′
   • Pro všechna nejednoduchá pravidla B → α přidáme do P′ pravidla A → α pro všechna A pro něž platí B ∈ N_A, tj. pro každého nejednoduché pravidlo najdeme všechny nonterminály A, které jdou jednoduchými pravidly přepsat na B, a vytvoříme všechny varianty pravidla, kde levou stranu nahradíme za A.

Převod vlastní gramatiky (N, Σ, P, S) na gramatiku bez levé rekurze (N′, Σ, P′, S).

Nonterminály vyjádříme jako N = {A₁, A₂, …, Aₙ} tj. zvolíme pořadí jednotlivých nonterminálů.

Gramatiku budeme transformovat tak, že je-li Aᵢ → α pravidlo pak α začíná buď terminálem nebo nonterminálem A_j, který je v pořadí až za Aᵢ (j > i).

1. i = 1 (tj. začneme prvním nonterminálem v pořadí)
2. Vezmeme všechna Aᵢ-pravidla, která jsou buď ve tvaru Aᵢ → Aᵢαₓ nebo Aᵢ → βₓ, kde β nezačíná nonterminálem, který je v pořadí před Aᵢ
   1. Přidáme nový nonterminál Aᵢ′ do N′
   2. Všechna Aᵢ-pravidla nahradíme za:
      • Aᵢ → β₁ | β₂ | … | βₓ (tj. přepisy na β zachováme)
      • Aᵢ → β₁Aᵢ′ | β₂Aᵢ′ | … | βₓAᵢ′ (tj. pro všechny přepisy na β vytvoříme pravidla s vpravo přidaným Aᵢ′)
      • Aᵢ′ → α₁ | α₂ | … | αₓ (tj. u přepisů na Aᵢα vytvoříme pravidla pouze s α)
      • Aᵢ′ → α₁Aᵢ′ | α₂Aᵢ′ | … | αₓAᵢ′ (tj. u přepisů na Aᵢα vytvoříme pravidla s odstraněným Aᵢ a vpravo přidaným Aᵢ′
      • Tím dosáhneme toho, že všechna Aᵢ-pravidla začínají buď terminálem nebo nonterminálem, který je v pořadí až za Aᵢ)
3. Pokud jsme již prošli všechny nontermínály (i = n) končíme
4. i++
5. Pro všechny dosud procházené nonterminály A_j (1 < j < i)
   1. Pravidlo Aᵢ → A_jα odstraníme
   2. Pro každé A_j-pravidlo (A_j → β) vytvoříme Aᵢ → βα, tj. vezmeme všechna Aᵢ-pravidla, jejichž pravá strana začíná nonterminálem A_j, který je v pořadí před Aᵢ, a nahradíme je za pravidla ve kterých je A_j nahrazeno všemi řetězci na které jej lze přepsat.
6. Jdeme na krok 2

Chomsky normal form

Přepisovací pravidla jsou pouze ve tvaru:

• A → BC
• A → a
• Případně S → ε pokud ε ∈ L(G) a S nesmí být na pravé straně žádného přepisovacího pravidla.

Převod vlastní gramatiky bez jednoduchých pravidel (N, Σ, P, S) na gramatiku v CNF (N′, Σ, P′, S′)

1. Množina P′ obsahuje všechny pravidla z P ve tvaru A → BC a A → a, případně S → ε.
2. Každé pravidlo tvaru A → X₁X₂…Xₖ (k > 2) přepíšeme do P′ jako sérii pravidel:
   1. A → X₁X₂′
   2. X₂′ → X₂X₃′
   3. …
   4. Xₖ₋₁′ → Xₖ₋₁Xₖ
3. Zavedeme nové non-terminální symboly A → X₂′…Xₖ₋₁′ (tj. pravidla mající pravou stranu delší než dva prvky rozdělíme na navazující sérii pravidel majících napravo jen dva prvky)
4. Ve všech pravidlech v P′ které nejsou ve tvaru A → a, kde se vyskytují na pravé straně terminály, nahradíme tyto terminály a za nové non-terminály A′ a přidáme pravidlo A′ → a (tj. nepovolená pravidla s terminály na pravé straně upravíme tak, že terminál nahradíme nonterminálem, který se přepisuje na původní terminál)

Greibach normal form

• Nejsou žádná ε pravidla
• Přepisovací pravidla ve tvaru A → aα kde aα ∈ N^*
• Případně S → ε pokud ε ∈ L(G) a S nesmí být na pravé straně žádného přepisovacího pravidla

Převod vlastní gramatiky bez levé rekurze (N, Σ, P, S) na gramatiku v GNF (N′, Σ, P′, S′):

1. Seřadíme všechny nonterminály tak, aby pravá strana žádného přepisovacího pravidla nezačínala nonterminálem, který je v pořadí před přepisovaným nonterminálem. (v podstatě stejná pořadí v jakém máme nonterminály během algoritmu odstranění levé rekurze): N = {A₁, A₂, …, Aₙ}
2. Postupně pro všechny nonterminály Aᵢ od Aₙ₋₁ sestupně po A₁:
   1. Pro každé pravidlo Aᵢ → A_jα:
      1. Odstraň toto pravidlo
      2. Pro všechna A_j-pravidla (A_jα → β) vytvoř nová pravidla ve tvaru Aᵢ → βα (tj. všechna pravidla jejichž pravé strana začíná nonterminálem rozepíšeme tento nonterminál na všechny možnosti na jaké jej lze přepsat)
   2. Po dokončení tohoto kroku všechny pravidla mají pravou stranu začínající terminálem.
   3. Ve všech pravidlech v P′ ve kterých se na pravé straně vyskytují terminály na jiné než první pozici nahradíme tyto terminály a za nové non-terminály A′ a přidáme pravidlo A′ → a (tj. nepovolená pravidla s terminály na pravé straně upravíme tak, že terminál nahradíme nonterminálem, který se přepisuje na původní terminál)