Formális nyelvek. Hogyan kell Chomsky-normálformára hozni az alábbi nyelvtant?

Chomsky-féle normálalak:

Ekkor csak X→y vagy X→YZ szabályok lehetnek, ahol y bármilyen terminális (betű), X,Y,Z pedig bármilyen nemterminális (változó, szimbólum).

I. Először üresszó-mentessé (ε mentessé) kell tenni a nyelvtant:

Csináljunk egy P' szabály-halmazt, amiben az ε csak egyetlen S'→ε helyettesítési szabályban szerepel.

Ezt így tehetjük:

Azon nemterminálisok (változó szimbólumok) halmaza, amik közvetlenül generálnak üresszót:

U₁ = {A,D}, hisz csak az A→ε és D→ε szabályoknál szerepel az ε.

Aztán bővíteni kell ezt azon nemterminálisokkal, amikből A vagy D generálódhat (szóval ha kihagyjuk a jobb oldalról A-t és D-t, akkor üreset kapunk):

U₂ = U₁ ∪ {S} = {S,A,D}

Tovább nem bővíthető a halmaz (B-ből vagy C-ből sose lesz ε).

Az U = {S,A,D} nemterminálisokból generálható az üresszó.

Mivel a startszó (S) benne van U-ban, ezért a G által generált nyelvben benne van az üresszó. Vagyis lesz majd egy S'→ε szabály.

A G-vel egyenértékű G' = <{a,b},{S',S,A,B,C,D},P',S'> nyelvtanban P' a következő szabályokból áll:

a) S' → S|ε (itt szerepel egyedül ε)

b) Az eredeti szabályok közül azok, amik nem ε-t generálják:

S → aAB|A

A → BD|aDBb

B → Da|bbAD

C → aDC

D → bCA|b

c) Be kell még venni az összes lehetséges helyettesítést, amit úgy kapunk, hogy az U = {S,A,D} lehetséges variációit egyszerűen elhagyjuk, és nem lesz üres a jobb oldal:

S → aB (aAB-ből elhagytuk A-t)

A → B (a BD-ből elhagytuk D-t)

A → aBb (az aDBb-ből elhagytuk D-t)

B → a (Da-ból elhagytuk D-t)

B → bbD|bbA|bb (bbAD-ből elhagytuk először A-t, aztán D-t, aztán mindkettőt)

C → aC (aDC-ből elhagytuk D-t)

D → bC (bCA-ból elhagytuk A-t)

Vagyis P' szabályai ezek: (Ha lenne két egyforma szabály, azt csak egyszer kell beírni persze)

S' → S|ε

S → aAB|aB|A

A → BD|B|aDBb|aBb

B → Da|a|bbAD|bbD|bbA|bb

C → aDC|aC

D → bCA|bC|b

Ezekkel a szabályokkal a G' nyelvtan ugyanazt a nyelvet generálja, mint G, beleértve az üresszót is.

A Chomsky normálalakhoz ki kell hagyni ebből az S' szabályait, és ez a harmadik nyelvtan a kiindulás:

G'' = <{a,b},{S,A,B,C,D},P'',S>

Ez az üresszótól eltekintve ugyanazt a nyelvet generálja, mint G. (Nem írom le P''-t, ugyanaz, mint P', csak nincs benne az első sor.)

Valójában G'-t nem is kellett volna leírni, lehetett volna eleve a G''-t, S' nélkül.

II. A következő lépés minden szabályt átalakítani X→y és X→YZ alakba. Először a terminálisoktól szabadulunk meg a jobb oldalon a nem X→y alakú szabályoknál. Ehhez új nemterminálisokat (szimbólumokat) is be kell vezetni: minden terminálishoz kell egy szimbólum, ami azt a terminálist generálja.

Most két terminális van, lesz két új szimbólum, E és F. Ezek a szabályok tartoznak hozzá:

E → a

F → b

Aztán minden olyan szabálynál, ahol keverve vannak terminálisok és nemterminálisok, a terminálisokat le kell cserélni az új szimbólumokra. Ezek lesznek a szabályok:

S → EAB|EB|A

A → BD|B|EDBF|EBF

B → DE|a|FFAD|FFD|FFA|FF

C → EDC|EC

D → FCA|FC|b

E → a

F → b

Szóval az összes a helyett E-t írtam, az összes b helyett F-et, kivéve, ahol egyedül állt az a vagy b.

III. Na most vannak még olyan szabályok, amiknek a jobb oldala 2-nél hosszabb. Azokat is 2 hosszúra kell alakítani. Ehhez megint új szimbólumokat kell bevezetni. Mondjuk egy X→ABC helyett azok lesznek, hogy X→AQ és Q→BC, ahol Q egy új szimbólum. 3-nál hosszabb esetben több új szimbólum is kell.

Most a G,H,I,J,K,L,M,N,O új szimbólumok jöttek be:

S → EG|EB|A

A → BD|B|EH|EI

B → DE|a|FJ|FL|FM|FF

C → EN|EC

D → FO|FC|b

E → a

F → b

G → AB

H → DI

I → BF

J → FK

K → AD

L → FD

M → FA

N → DC

O → CA

Figyeld meg, hogy az A→EDBF illetve A→EBF szabályokból mi lett. EDBF-ből lett EH, ahol H-ból DBF kellett volna legyen, ezért az megint tovább bomlott I-re: H→DI és I→BF. Aztán mivel már lett BF-et generáló szabály, azt fel lehetett hasznáni az A→EBF esetén A→EI alakban.

IV. Ez már majdnem jó, de vannak még benne X→Y alakú szabályok (pl. S→A). Ezektől meg kell szabadulni.

a) Ahhoz először fel kell térképezni, hogy mikből lesz egy vagy több lépésben egyetlen nemterminális (nagybetű).

Most a jobb oldalon kétféle nemterminális szerepel magában: A és B. Mindkettőt térképezzük fel: csináljunk U(A) és U(B) halmazokat:

- A-t egyedül S generálja közvetlenül. S-et nem generálja semmi, tehát U(A) ennyi:

U(A) = {S}

- B-t egyedül A generálja közvetlenül. Az előbb már láttuk, hogy A generálódik S-ből, azt is hozzá kell venni:

U(B) = {A,S}

b) Hagyjuk el a jobb oldalról az egyedüli nemterminálisokat:

S → EG|EB

A → BD|EH|EI

B → DE|a|FJ|FL|FM|FF

C → EN|EC

D → FO|FC|b

E → a

F → b

G → AB

H → DI

I → BF

J → FK

K → AD

L → FD

M → FA

N → DC

O → CA

Most csak az S és az A sora változott.

c) U(A) = {S}, vagyis A generálódik S-ből, ezért ismételjük meg az A sort úgy, hogy átnevezzük S-re is:

S → EG|EB

A → BD|EH|EI

  S→BD|EH|EI

B → DE|a|FJ|FL|FM|FF

C → EN|EC

... a többit le se írom újra.

U(B) = {A,S}, vagyis B generálódik A-ból meg S-ből, ezért ismételjük meg a B sort (vagy ha több sor is lenne, mindet) úgy, hogy átnevezzük A-ra meg S-re is:

S → EG|EB

A → BD|EH|EI

  S→BD|EH|EI

B → DE|a|FJ|FL|FM|FF

  A→DE|a|FJ|FL|FM|FF

  S→DE|a|FJ|FL|FM|FF

C → EN|EC

... a többit le se írom újra.

d) Végül egy sorba rakhatjuk az azonos bal oldalú sorokat:

S → EG|EB|BD|EH|EI|DE|a|FJ|FL|FM|FF

A → BD|EH|EI|DE|a|FJ|FL|FM|FF

B → DE|a|FJ|FL|FM|FF

C → EN|EC

... a többit le se írom újra.

--

Kész vagyunk. Ez lett a végső nyelvtan:

G''' = <{a,b},{S,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O},P''',S>

ahol P''' a következő szabályokból áll:

S → EG|EB|BD|EH|EI|DE|a|FJ|FL|FM|FF

A → BD|EH|EI|DE|a|FJ|FL|FM|FF

B → DE|a|FJ|FL|FM|FF

C → EN|EC

D → FO|FC|b

E → a

F → b

G → AB

H → DI

I → BF

J → FK

K → AD

L → FD

M → FA

N → DC

O → CA

Ez Chomsky normálalakú. Az üresszótól eltekintve ugyanazt a nyelvet generálja, mint G.