Forma Normal Chomsky (Chomsky Normal Form (CNF))

DEFINISAUN CNF NO GNF

Komprensivamente, hanesan ohin temi ona katak existe diferensa entre CNF no GNF iha prosesu konversaun husi produsaun Gramátika Kontekstu Livre (Free Context Grammar (CFG)) nian. Ne’e duni, hakerek na’in hafahe no esplika klaramente konteúdu rua ne’e ho nia ezemplu balu atu bele komprende lalais liu tán.

Forma Normal Chomsky (Chomsky Normal Form (CNF))

Definisaun CNF

Liafuan Chomsky mai husi sientista ida ho naran Noam Chomsky. Chomsky Normal Form (CNF) nu’udár forma normal ida ne’ebé funsiona tebes ba Context Free Grammar (CFG). Forma Normal Chomsky bele halo ka konverte husi gramátika kontekstu livre ne’ebé iha ona simplifikasaun mak halakon produsaun useless, unit, no e.

 Forma  no Regra Konversaun Produtu CNF

Teorikamente, it abele halo Gramátika Kontekstu Livre ida sai fali Forma Normal Chomsky ho rikizitu sira mak hanesan CFG refere :

·      Labele existe produsaun useless

·      Labele existe produsaun Unit

·      Labele existe produsaun e

Forma Normal Chomsky mak Gramátika kontekstu livre no kada nia produsaun ho forma:
 

Regra produsaun ho forma normal Chomsky nia parte kuanan existe de’it terminal ida ka variavel rua.

Iha prosesu konversaun produsaun CFG ba CNF presiza mos regra importante sira mak hanesan imajen tuir mai.

Diferensa CFG no CNF

Ezemplu Konversaun CFG ba CNF

Ø Ezemplu Dahuluk

Asumi gramátika kontekstu livre ( ne’ebé laiha ona produsaun useless, unit no ε) hanesan tuir mai:

S à aB | SS | c

B à BBB | cd | a

Konverta CFG refere ba CNF !

Resposta :

Pasu 1

Husik ka mantein regras produsaun ne’ebé ho forma CNF ona:

S à SS

S à c

B à a

Pasu 2

Halo substituisaun regras produsaun ne’ebé seidauk iha forma CNF:

CFG : S à aB | SS | c

            B à BBB | cd | a

S à aB                     =>       S à Z1 B

B à BBB                 =>       B à Z2 B

B à cd=>  à Z3d    =>       B à Z3 Z4

Forma no hamosu símbolu variavel foun no regras produsaun foun:

•     Z1 à a                 Z3 à c

•     Z2 à BB             Z4 à d

Rezultadu ikus CFG ne’ebé konverte ona ba CNF:

S à Z1B | SS | c                  Z2 à BB

B à Z2 B | Z3 Z4 | a            Z3 à c

Z1 à a                                  Z4 à d

Ø Ezemplu Daruak

Asumi gramátika kontekstu livre ( ne’ebé laiha ona produsaun useless, unit no ε) hanesan tuir mai:

S à bA | aB

A à bAA | aS | a

B à aBB | bS | b

Konverta CFG refere ba CNF !

Resposta :

Pasu 1

Husik ka mantein regras produsaun ne’ebé ho forma CNF ona:

A à a

B à b

Pasu 2

Halo substituisaun regras produsaun ne’ebé seidauk iha forma CNF:

CFG : S à bA | aB

            A à bAA | aS | a

            B à aBB | bS | b

S à bA => S à P₁A

S à aB => S à P₂B

A à bAA => A à P₁AA, A à P₁AA => A à P₁P₃

A à aS => A à P₂S

A à a

B à aBB => B à P₂BB, B à P₂BB  => B à P₂P4

B à bS => B à P₁S

B => b

Forma no hamosu símbolu variavel foun no regras produsaun foun:

•     P₁ à b                  P₃ à AA

•     P₂ à a                  P₄ à BB

P₁ = Q, P₂ = R, P₃ = T, P₄ = V

Rezultadu ikus CFG ne’ebé konverte ona ba CNF:

S à QA                   B à b

S à RB                   Q à b

A à QT                    R à a

A à  RS                   T à AA

A à a                       V à BB

B à RV

B à QS