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

1
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A
  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ᵢ
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

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ᵢ
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Transformace gramatik (odstranění ε-pravidel)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Transformace gramatik (Odstranění levé rekurze)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Chomského normální forma (CNF)

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Greibachové normální forma (GNF)

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly