====== Transformace a normální formy bezkontextových gramatik ======
===== Derivace a derivační stromy =====
Gramatika (//N//, //Σ//, //P//, //S//)
* **[[wp>Parse tree|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í
===== Transformace =====
[[pitel:tin:ukoly:2010:2#priklad_3|Úkol z TINu 2010]], [[pitel:tin:ukoly:2011:2#priklad_5|Úkol z TINu 2011]]
==== Odstranění nedostupných symbolů ====
Převod gramatiky (//N//, //Σ//, //P//, //S//) na gramatiku bez nedostupných stavů (//N//′, //Σ//′, //P//′, //S//)
- Najdeme všechny dostupné terminály a nonterminály
- //i// = 0
- //V//₀ = {//S//} (tj. v nultém kroku je dostupný pouze počáteční stav)
- ''repeat''
- //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)
- //i//++ (tj. přejdeme k dalšímu kroku)
- ''until'' //Vᵢ//₊₁ = //Vᵢ//₋₁ (tj. končíme pokud se nám v posledním kroku množina dostupných nezměnila)
- 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ᵢ//
==== Odstranění zbytečných symbolů ====
Převod gramatiky (//N//, //Σ//, //P//, //S//) na gramatiku bez nedostupných stavů (//N//′, //Σ//, //P//′, //S//)
- Nalezení nonterminálů, které produkují terminální řetězce
- //i// = 0
- //N//₀ = ∅ (tj. v nultém kroku začínáme s prázdnou množinou nonterminálů generujících terminální řetězce)
- ''repeat''
- //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)
- //i//++ (tj. přejdeme k dalšímu kroku)
- until //Nᵢ//₊₁ = //Nᵢ//₋₁ (tj. končíme pokud se nám v posledním kroku množina nezměnila)
- 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ᵢ//
- Odstraníme nedostupné symboly z gramatiky
==== Odstranění ε-pravidel ====
Převod gramatiky (//N//, //Σ//, //P//, //S//) na gramatiku bez //ε//-pravidel (//N//′, //Σ//′, //P//′, //S//′)
- 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ᵢ//
- 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
- Zavedeme nový počáteční nonterminál //S//′
- Jestliže je //S// v //Nε// pak přidáme do //P//′ pravidla //S//′ -> //ε// a //S//′ -> //S//
==== Odstranění jednoduchých pravidel ====
Převod gramatiky bez //ε//-pravidel (//N//, //Σ//, //P//, //S//) na gramatiku bez jednoduchých pravidel (//N//, //Σ//, //P//′, //S//)
- Pro každé //A// ∈ //N// sestrojíme množinu //NA// = {//B// | //A// =>* //B//}
- //i// = 0
- //N//₀ = {//A//}
- ''repeat''
- //Nᵢ//₊₁ = //Nᵢ// ∪ {//C// | //B// -> //C// ∈ //P// ∧ //B// ∈ //Nᵢ//}
- //i//++
- ''until'' //Nᵢ// = //Nᵢ//₋₁ (tj. končíme pokud se nám v posledním kroku množina nezměnila)
- //NA// = //Nᵢ//
- 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// ∈ //NA//, 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//.
==== Odstranění levé rekurze ====
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 //Aj//, který je v pořadí až za //Aᵢ// (//j// > //i//).
- //i// = 1 (tj. začneme prvním nonterminálem v pořadí)
- 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ᵢ//
- Přidáme nový nonterminál //Aᵢ//′ do //N//′
- 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ᵢ//)
- Pokud jsme již prošli všechny nontermínály (//i// = //n//) končíme
- //i//++
- Pro všechny dosud procházené nonterminály //Aj// (1 < //j// < //i//)
- Pravidlo //Aᵢ// -> //Ajα// odstraníme
- Pro každé //Aj//-pravidlo (//Aj// -> //β//) vytvoříme //Aᵢ// -> //βα//, tj. vezmeme všechna //Aᵢ//-pravidla, jejichž pravá strana začíná nonterminálem //Aj//, který je v pořadí před //Aᵢ//, a nahradíme je za pravidla ve kterých je //Aj// nahrazeno všemi řetězci na které jej lze přepsat.
- Jdeme na krok 2
===== Normální formy =====
==== Chomského normální forma (CNF) ====
[[wp>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//′)
- Množina //P//′ obsahuje všechny pravidla z //P// ve tvaru //A// -> //BC// a //A// -> //a//, případně //S// -> //ε//.
- Každé pravidlo tvaru //A// -> //X//₁//X//₂...//Xₖ// (//k// > //2//) přepíšeme do //P//′ jako sérii pravidel:
- //A// -> //X//₁//X//₂′
- //X//₂′ -> //X//₂//X//₃′
- ...
- //Xₖ//₋₁′ -> //Xₖ//₋₁//Xₖ//
- 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)
- 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)
==== Greibachové normální forma (GNF) ====
[[wp>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//′):
- 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ₙ//}
- Postupně pro všechny nonterminály //Aᵢ// od //Aₙ//₋₁ sestupně po //A//₁:
- Pro každé pravidlo //Aᵢ// -> //Ajα//:
- Odstraň toto pravidlo
- Pro všechna //Aj//-pravidla (//Ajα// -> //β//) 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)
- Po dokončení tohoto kroku všechny pravidla mají pravou stranu začínající terminálem.
- 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)