Normalne oblike gramatik

Normalna oblika po Chomskem

Oblika:

A → BC

A → α

ne more generirati prazne besede

Naj bo G=<V,T,P,S> KNG → ∃G' v NOC(Normalna Oblika po Chomskem),tako da L(G')=L(G)\{ε}

Postopek

• odpravljanje ε-produkcij (A → ε )
• odpravljanje enotskih produkcij (A → B)
• odpravljanje nekoristnih simbolov
  • ki se ne razvijejo v niz končnih simbolov
  • ki niso dosegljivi iz začetnega simbola

karkoli neuporabnega najdemo, brišemo vse produkcije, kjer se pojavi neuporaben simbol

• spemenimo v obliko po Chomskem z dodajanjem novih spremenljivk

• ponavljajoče spremenljivke moramo tudi zamenjati z novimi (npr A → XBB gre v A → XC, C → BB)
• v končne simbole spremenimo z uvedbo dodatnih spremenljivk (npr A → aB gre v A → QB in Q → a)
• ne smemo imeti večje dolžine produkcij kot 2!

Normalna oblika po Greibachovi

Oblika:

• A_i → aA_j ; i ≤ j
• desno rekurzivna oblika

• izhajamo iz oblike po Chomskem

Postopek

0. korak

• Preimenujemo spremenjlivke v A1,A2,A3,... ( pomenbno kako označimo, saj si s s pravilno izbiro močno olajšamo nadaljne delo)

1. korak

• dvignemo produkcije:
  • če je A_i → A_jα in i>j zamenjamo A_i → A_jα z A_i → βα za vsak β:A_j→β

(z besedo) dvignemo produkcije tako da velja oblika po Greibach-ov (zamenjamo produkcije na prvem mestu); rekurzijo, kjer se pojavi pustimo

2. korak

• Leva rekurzija v desno
  • če A_i→A_iα zamenjaj A_iα z B_i → α|αB_i
  • za vsako A_i→Xα pri X≠A_i dodaj A_i→XαB_i

(z besedo) rekurzijo popravimo tako, da dodamo B -> ostanek(α)|ostanek(α)B, v A pa pripišemo vse kombinacije z B na koncu

3. korak

• spremenimo vse produkcije v obliko A → aα, kjer α lahko vsebuje končne simbole

(z besedo) poskrbimo da je povsod na prvem mestu končni simbol)

4. korak

• substitucija višjih spremenjljivk; spremenimo α tako, da ne vsebuje končnih simbolov

(z besedo) uvedemo dodatne spremenjljivke, da imamo samo na začetku končni simbol)

Zunanje povezave

• http://www.cs.ucr.edu/~marek/TEACHING/CS150_W06/NOTES/GREIBACH_NORMAL_FORM/greibach.pdf