Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- pitel:msz:bezkontextove_gramatiky [03. 07. 2012, 11.53:30] – upraveno mimo DokuWiki 127.0.0.1
+++ pitel:msz:bezkontextove_gramatiky [30. 12. 2022, 13.43:01] (aktuální) – upraveno mimo DokuWiki 127.0.0.1
@@ Řádek 1: / Řádek 1: @@
+====== 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// =><sup>*</sup> //α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// =><sup>*</sup> //α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ᵢ// ∪ //Σ//)<sup>*</sup>} (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<sub>ε</sub>//
+    * Postup je obdobný jako krok 1 algoritmu odstranění zbytečných symbolů pouze //Nᵢ//₊₁ = //Nᵢ// ∪ {//A// | //A// -> //α// ∈ //P// ∧ //α// ∈ (//Nᵢ// ∪ {//ε//})<sup>*</sup>}, //N<sub>ε</sub>// = //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<sub>ε</sub>// a žádný symbol //αᵢ// není v //N<sub>ε</sub>// 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<sub>ε</sub>// 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 //N<sub>A</sub>// = {//B// | //A// =><sup>*</sup> //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)
+    - //N<sub>A</sub>// = //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// ∈ //N<sub>A</sub>//, 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 //A<sub>j</sub>//, 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 //A<sub>j</sub>// (1 < //j// < //i//)
+    - Pravidlo //Aᵢ// -> //A<sub>j</sub>α// odstraníme
+    - Pro každé //A<sub>j</sub>//-pravidlo (//A<sub>j</sub>// -> //β//) vytvoříme //Aᵢ// -> //βα//, tj. vezmeme všechna //Aᵢ//-pravidla, jejichž pravá strana začíná nonterminálem //A<sub>j</sub>//, který je v pořadí před //Aᵢ//, a nahradíme je za pravidla ve kterých je //A<sub>j</sub>// 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//<sup>*</sup>
+  * 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ᵢ// -> //A<sub>j</sub>α//:
+      - Odstraň toto pravidlo
+      - Pro všechna //A<sub>j</sub>//-pravidla (//A<sub>j</sub>α// -> //β//) 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)

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku