Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revizePředchozí verze | |||
pitel:msz:bezkontextove_gramatiky [02. 04. 2013, 12.16:52] – [Transformace] linky pitel | 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> | ||
+ | * 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á/ | ||
+ | * Při sestavování je vždy přepsán nejlevější/ | ||
+ | * **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// =>< | ||
+ | * **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// =>< | ||
+ | * **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á | ||
+ | * **// | ||
+ | * //A// -> //ε// (přepisují nonterminál na prázdný řetezec) | ||
+ | * **// | ||
+ | * 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 // | ||
+ | * **Rekurzivní pravidla** | ||
+ | * Rekurzivní zleva: //A// -> //Aα// | ||
+ | * Rekurzivní zprava: //A// -> //αA// | ||
+ | * Rekurzivní: | ||
+ | * Každý bezkontextový jazyk lze generovat gramatikou bez levé rekurze | ||
+ | * Všechna pravidla s levou rekurzí lze nahradit pravidly s pravou rekurzí | ||
+ | ===== Transformace ===== | ||
+ | [[pitel: | ||
+ | ==== 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//₀ = {// | ||
+ | - '' | ||
+ | - // | ||
+ | - //i//++ (tj. přejdeme k dalšímu kroku) | ||
+ | - '' | ||
+ | - 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ů, | ||
+ | - //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) | ||
+ | - '' | ||
+ | - // | ||
+ | - //i//++ (tj. přejdeme k dalšímu kroku) | ||
+ | - until // | ||
+ | - Vytvoříme gramatiku bez nonterminálů, | ||
+ | * //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 // | ||
+ | - Sestavení množiny nonterminálů, | ||
+ | * Postup je obdobný jako krok 1 algoritmu odstranění zbytečných symbolů pouze // | ||
+ | - Sestavíme novou množinu přepisovacích pravidel //P//′ | ||
+ | * Jestliže //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 // | ||
+ | |||
+ | ==== Odstranění jednoduchých pravidel ==== | ||
+ | Převod gramatiky bez // | ||
+ | - Pro každé //A// ∈ //N// sestrojíme množinu // | ||
+ | - //i// = 0 | ||
+ | - //N//₀ = {//A//} | ||
+ | - '' | ||
+ | - // | ||
+ | - //i//++ | ||
+ | - '' | ||
+ | - // | ||
+ | - 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// ∈ // | ||
+ | ==== 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 // | ||
+ | |||
+ | - //i// = 1 (tj. začneme prvním nonterminálem v pořadí) | ||
+ | - Vezmeme všechna // | ||
+ | - Přidáme nový nonterminál //Aᵢ//′ do //N//′ | ||
+ | - Všechna // | ||
+ | * //Aᵢ// -> //β//₁ | //β//₂ | ... | //βₓ// (tj. přepisy na //β// zachováme) | ||
+ | * //Aᵢ// -> // | ||
+ | * //Aᵢ//′ -> //α//₁ | //α//₂ | ... | //αₓ// (tj. u přepisů na //Aᵢα// vytvoříme pravidla pouze s //α//) | ||
+ | * //Aᵢ//′ -> // | ||
+ | * Tím dosáhneme toho, že všechna // | ||
+ | - Pokud jsme již prošli všechny nontermínály (//i// = //n//) končíme | ||
+ | - //i//++ | ||
+ | - Pro všechny dosud procházené nonterminály // | ||
+ | - Pravidlo //Aᵢ// -> // | ||
+ | - Pro každé // | ||
+ | - Jdeme na krok 2 | ||
+ | ===== Normální formy ===== | ||
+ | ==== Chomského normální forma (CNF) ==== | ||
+ | [[wp> | ||
+ | |||
+ | Přepisovací pravidla jsou pouze ve tvaru: | ||
+ | * //A// -> //BC// | ||
+ | * //A// -> //a// | ||
+ | * Případně //S// -> //ε// pokud //ε// ∈ // | ||
+ | |||
+ | 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// -> // | ||
+ | - //A// -> // | ||
+ | - //X//₂′ -> // | ||
+ | - ... | ||
+ | - // | ||
+ | - Zavedeme nové non-terminální symboly //A// -> // | ||
+ | - 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, | ||
+ | ==== Greibachové normální forma (GNF) ==== | ||
+ | [[wp> | ||
+ | |||
+ | * Nejsou žádná //ε// pravidla | ||
+ | * Přepisovací pravidla ve tvaru //A// -> //aα// kde //aα// ∈ // | ||
+ | * Případně //S// -> //ε// pokud //ε// ∈ // | ||
+ | |||
+ | 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, | ||
+ | - Postupně pro všechny nonterminály //Aᵢ// od // | ||
+ | - Pro každé pravidlo //Aᵢ// -> // | ||
+ | - Odstraň toto pravidlo | ||
+ | - Pro všechna // | ||
+ | - 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, |