20 - Transformace a normální formy bezkontextových gramatik

Question 1

Gramatika, derivace, derivační stromy a větné formy

Answer 1

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 => β

Question 2

Základní pojy: pravidla, zbytečné symboly, vlastní gramatika, rekurze

Answer 2

ε-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í!

Question 3

Transformace gramatik (odstranění nedostupných symbolů)

Answer 3

1. máme počáteční stav
2. 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
3. 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ᵢ

Question 4

Transformace gramatik (odstranění zbytečných symbolů)

Answer 4

jdeme prostě od konce (od terminálů k nonterminálům)

1. začínáme s prázdnou množinou nonterminálů generujících terminální řetězce
2. 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
3. Novou gramatiku:
   ○ N′ = Nᵢ
   ○ P′ ⊂ P obsahuje pouze pravidla používající pouze symboly z Nᵢ

Question 5

Transformace gramatik (odstranění ε-pravidel)

Answer 5

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

Question 6

Transformace gramatik (Odstranění jednoduchých pravidel)

Answer 6

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

Question 7

Transformace gramatik (Odstranění levé rekurze)

Answer 7

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ᵢ)

Question 8

Chomského normální forma (CNF)

Answer 8

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:

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₂…Xk (k > 2) přepíšeme do P′ jako sérii pravidel:
   a. A → X₁X₂′
   b. X₂′ → X₂X₃′
3. (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. (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:

1. Transformace do vlastní gramatiky
2. Bez jednoduchých pravidel
3. Chomského normální forma

Question 9

Greibachové normální forma (GNF)

Answer 9

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.

1. Odstranění E pravidel
2. Odstranění levé rekurze
3. Relace uspořádání
4. Dosazení v pořadí inverznímu k relaci uspořádání
5. GNF