Forma Normal Greibach - Greibach Normal Form GNF

  Forma Normal Greibach ( Greibach Normal Form (GNF))

Definisaun GNF

          Forma Normal Greibach nu’udár forma normal ida ne’ebé iha konsekénsia teórika no prátika. Iha Forma Normal Greibach ita limita pozisaun aparesimentu terminal no variavel sira.

Forma  no Regra Konversaun Produtu GNF

          Gramátika Kontekstu Livre ida bele kategoria nu’udár Forma Normal Greibach se kada regra produsaun ho forma:

A à aa

a : símbolu terminal (mesak)

a : símbolu variavel (V*)

          Ho liafuan seluk, Gramátika Kontekstu Livre bele ho Forma Normal Greibach se rezultadu produsaun ( parte kuanan) hahú ho símbolu terminal ida, tuir mai bele hatutan ho série símbolu variável sira.

Ezemplu grámatika kontekstu livre ne’ebé bele hola parte forma normal greibach:

S à a | aAB

A à aB

B à cS

          Atu bele modifika sai forma normal Greibach, forma gramátika refere tenki tuir kritéria mak:

·    Ho Forma Normal Greibach ona

·    La ho karákter rekursivu iha parte karuk

·    La rezulta e

          Kada substituisaun ne’ebé halo ba símbolu variavel dahuluk iha parte kuanan ( ba regras produsaun ne’ebé seidauk ho forma normal Greibach) nia prinsípiu mak:

·    Husik ka mantéin regras produsaun ne’ebé ho forma normal Greibach ona.

·    Defini sorting (Pengurutan) símbolu variavel, bazeia ba kondisaun regras  produsaun ne’ebé iha no halo sorting ne’ebé hafasil iha prosesu tuir mai.

·    Halo mudansa ba regras produsaun ne’ebé seidauk kumpri definisaun sorting refere.

·    Prosesu substituisaun fila (mundur) hahú husi regras produsaun ho sorting ikus liu

·    Halu mos substituisaun fila ba regras produsaun foun ne’ebé mosu.

 Ezemplu Konversaun CFG ba GNF

            Asumi gramátika kontekstu livre hanesan tuir mai:

S à CA                    C à DD

A à a | d                  D à AB

B à b

Konverta CFG refere ba GNF !

Resposta :

Pasu 1

Defini sorting símbolu variavel, hanesan S, A, B, C, D (S<A<B<C<D)

Sorting refere ita bele define rasik.

Pasu 2

Identifika regras produsaun ne’ebé nia símbolu dahuluk iha parte kuanan mak símbolu variavel, kumpri ona definisaun sorting variavel ka seidauk:

S à CA ( kumpri ona tamba S<C)

C à DD (kumpri ona tamba C<D)

D à AB (seidauk kumpri tamba D>A)

Ida ne’ebé seidauk kumpri sorting ne’ebé ita define mak D à AB, tamba parte karuk > símbolu dahuluk husi parte loos. Entaun ita halo substituisaun ba símbolu variavel A, regras produsaun sai:

D à aB | dB

Pasu 3

Depois de regras produsaun sira kumpri ona definisaun sorting variavel, ita halo substituisaun fila (mundur) ba regras produsaun ne’ebé seidauk ho forma normal Greibach:

C à DD => C àaBD | dBD

S à CA => S à aBDA | dBDA

Rezultadu ikus:

S à aBDA | dBDA

A à a | d

B à b

C à aBD | dBD

D à aB |dB