20 - Transformace a normální formy bezkontextových gramatik Flashcards
Gramatika, derivace, derivační stromy a větné formy
Gramatika (N,Σ,P,S)
Gramatika G = (N , Σ, P , S) je bezkontextová,pokud jsou pravidla ve tvaru: A→α, A∈N, α∈(N⋃Σ)*
Levá/pravá derivace
Při sestavování je vždy přepsán nejlevější/nejpravější nonterminál.
Víceznačnost
Věta je víceznačná pokud existuje více derivačních stromů tvořících jednu větu.
• Existují jazyky, které nelze generovat bez víceznačnosti
• Gramatika, která obsahuje cykly je vždy víceznačná
Fráze větné formy = je to řetězec (část věty) tvořený terminály, vygenerovaný z nějakého neterminálu. - Fráze jsou podstromy v derivačním stromu.
• řaday symbolů na koncových uzlech jednopatrového podstormu derivačního stromu
• β je frází větné formy pokud (fráze je přímo derivovaná z nonterminálu A) - S =>^* alpha A gamma AND A => β
Základní pojy: pravidla, zbytečné symboly, vlastní gramatika, rekurze
ε-pravidlo - A→ϵ (přepisují nonterminál na prázdný řetezec).
A-pravidla - Všechna pravidla, která mají A na levé straně, přičemž A je nonterminál.
Jednoduchá pravidla - 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ětu).
Cyklus
• A→^+ A
• aby byly cykly možné je nutné aby gramatika obsahovala jednoduchá pravidla
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 gramatik (odstranění nedostupných symbolů)
- máme počáteční stav
- do množiny dostupných přidáme všechny terminály a nonterminály, které lze získat přepisem z některého nonterminálu z množiny dostupných z předchozího kroku
- Novou gramatiku sestavíme jako průniky s původníma:
○ 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ᵢ
Transformace gramatik (odstranění zbytečných symbolů)
jdeme prostě od konce (od terminálů k nonterminálům)
- začínáme s prázdnou množinou nonterminálů generujících terminální řetězce
- do množiny přidáme všechny NON-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
- Novou gramatiku:
○ N′ = Nᵢ
○ P′ ⊂ P obsahuje pouze pravidla používající pouze symboly z Nᵢ
Transformace gramatik (odstranění ε-pravidel)
od každého pravidla sestavíme všechny možné kombinace, kde jsou jednotlivé částí přepsatelné na ε vynechány
Jestliže je S v Nε pak přidáme do P′ pravidla S′ → ε a S′ → S
Transformace gramatik (Odstranění jednoduchých pravidel)
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
Transformace gramatik (Odstranění levé rekurze)
A→Aα_1∣…∣Aα_n∣β_1∣…∣β_m
§ 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ᵢ)
Chomského normální forma (CNF)
Důkaz pumping lemma a syntaktická analýza!
Obecně k čemu obecně slouží normální formy (prakticky (překladače), i teoreticky (důkazy))
Chomského normální forma je tvar formální gramatiky ve které jsou všechna odvozovací pravidla tvaru:
• A → BC
• A → a
• S → ε pokud ε ∈ L(G) a S nesmí být na pravé straně žádného přepisovacího pravidla.
○ a je NEterminál, velká písmena jsou terminály.
○ derivační strom CNF je binární !!!
Derivační strom (= syntaktický strom) • Vnitřní uzly jsou neterminály, tedy prvky z N • Koncové uzly jsou terminály Σ • Kořen stromu je S • Hrany odpovídají přepisovacím pravidlům gramatiky P • Označení koncových uzlů zleva doprava tvoří větnou formu (nebo větu) 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 - různé pořadí v jakém byly vybírány nonterminály pro přímé derivace).
Transformace:
- 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₂…Xk (k > 2) přepíšeme do P′ jako sérii pravidel:
a. A → X₁X₂′
b. X₂′ → 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)¨
- (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)
Kroky:
- Transformace do vlastní gramatiky
- Bez jednoduchých pravidel
- Chomského normální forma
Greibachové normální forma (GNF)
Graibachové normální forma (GNF) je tvar formální gramatiky, ve které mají všechny odvozující pravidla tvar:
• A → aα kde α ∈ N* //tedy A→aA_1 A_2…A_n
• S → ε pokud ε ∈ L(G) a S nesmí být na pravé straně žádného přepisovacího pravidla
○ jestli na konci stačí pouze jeden nonterminál (odpovědí je, že nestačí, jinak by to byla regulární gramatika).
Nejsou žádná ε pravidla.
- Odstranění E pravidel
- Odstranění levé rekurze
- Relace uspořádání
- Dosazení v pořadí inverznímu k relaci uspořádání
- GNF