7.3. Normálformák a környezetfüggetlen nyelvtanokhoz

Gyakorlati szempontból fontos lehet, hogy a nyelvtant minimalizáljuk olyan értelemben, hogy megszabadulunk az olyan felesleges nemterminálisoktól, amik egyetlen termináló levezetésben sem jelennek meg. Egy A nemterminális két okból lehet felesleges:

- A nem vezethető be mondatformában, vagyis nincs olyan szabálysorozat, hogy az S mondatszimbólumból indulva valamilyen u A v mondatformát kapjunk (valamilyen u, v∈(NT)* szavakra).

- az A- ból nem lehet terminálni, vagyis nincs olyan wT *, hogy A* w lenne.

Az első típusba tartozó felesleges nemterminálisokat a következőképpen határozhatjuk meg egy G=(N, T, S, H) nyelvtan esetén:

Legyen U 0={S}.

Legyen U i+1=U i ∪{A | létezik Bu A vH, AN, BU i , u, v∈(NT)*} ( i ≥ 0 )

Ekkor az N végessége miatt van olyan i hogy U i =U i+1, és ekkor az NU i nemterminálisok feleslegesek, mert nem érhetőek el S- ből kezdődő levezetésekkel.

A második típusba tartozó felelsleges nemterminálisok meghatározása egy G=(N, T, S, H) nyelvtan esetén a következő rekurzív módon történhet:

Legyen U 0={A | létezik A → wH, AN, wT *}.

Legyen U i+1=U i ∪{A | létezik A → uH, AN, u∈(U i T)*} ( i ≥ 0 )

Ekkor az N végessége miatt van olyan i hogy U i =U i+1, és ekkor az NU i nemterminálisok feleslegesek, mert belőlük nem vezethető le terminális (vagy üres) szórész. Ha az S nincs benne az U i halmazban, akkor a generált nyelv üres.

Ha G nemüres nyelvet generál, akkor világos, hogy az így meghatározott felesleges nemterminálisokat, és az összes olyan szabályt, amely tartalmaz ilyen nemterminálist (akár a bal, akár a jobboldalán) elhagyva a kapott G ' nyelvtan ekvivalens az eredetivel: a termináló levezetések megmaradnak, így a generált nyelv nem változik.

Ha speciálisan reguláris nyelvtanból (vagy ennek megfelelő véges automatából) indulunk ki, akkor az első rész éppen a startszóból (vagyis a kezdőállapotból) való elérhetőséget jelenti. A második rész, vagyis azon nemterminálisok (állapotok) összegyűjtése, amiből nem tudunk terminálni a teljesen definiált determinisztikus véges automata esetén az egyetlen nyelő állapotnak felel meg.

A fejezet további részében két fontos normálformát mutatunk be, az elsőnél algoritmust is adunk arra, hogy egy tetszőleges környezetfüggetlen nyelvtanhoz vele ekvivalenset állítsunk elő. Természetesen, ha nem akarunk feleslegesen sok szabállyal dolgozni, akkor célszerű a normálformákat az imént bemutatott felesleges nemterminálisokat már nem tartalmazó nyelvtanokra meghatározni.

7.3.1. Chomsky-féle normálalak

Egy nyelvtant λ- mentesnek nevezünk, ha a szabályok jobb oldalán egyáltalán nem fordul elő a λ.

Itt jegyezzük meg, hogy minden 2-típusú λL nyelv esetén megadható olyan 2-típusú λ- mentes grammatika ami L- et generálja (lásd Üresszó-lemma). Ha viszont λL, akkor igaz az, hogy megadható olyan 2-típusú λ- mentes G grammatika ami a L∖{λ} nyelvet generálja. (Ilyenkor G nemterminális halmazát kiegészítve S ' új mondatszimbólummal, és a H szabályrendszert kiegészítve az S ' → λ, S ' → S szabályokkal kapunk egy L- et generáló nyelvtant.)

14. Definíció. Egy környezetfüggetlen nyelvtanról azt mondjuk, hogy Chomsky-féle normálalakban van, ha minden szabálya A → a vagy A → B C alakú, ahol A, B, CN és aT. ★

Minden λ- mentes környezetfüggetlen nyelv generálható olyan nyelvtannal, amely Chomsky-féle normálalakú. Avagy, kicsit másképp fogalmazva:

46. Tétel. Minden G környezetfüggetlen nyelvtanhoz van olyan vele ekvivalens környezetfüggetlen G C h nyelvtan, amely Chomsky-féle normálalakú.

Bizonyítás. Ha a G=(N, T, S, H) nyelvtan nem λ- mentes, vagyis van benne olyan szabály, aminek jobboldala az üresszó, akkor először alkalmazzuk rá az Üresszó-lemma -t, és legyen G '=(N, T, S, H , ) az a nyelvtan, amit az üresszó lemmánál ismertetett algoritmussal létrehozunk a G által generált nyelv λ- mentes részének generálására, ekkor G és G ' ekvivalensek (az általuk generált nyelvek különbsége legfeljebb az üresszót tartalmazza) és G' λ- mentes.

Hozzuk a nyelvtanunkat olyan alakra, hogy terminális jel csak A → a alakú szabályokban (AN, aT) forduljon elő: Vezessük be az X a új nemterminálisokat a következő módón: legyen N t ={X a |aT} és N ''=NN t , ahol N t N=∅. Továbbá a H ' minden nem Aa(AN, aT) alakú szabályára: cseréljük ki a szabály jobboldalán található a terminálisokat a nekik megfelelő imént bevezetett X a nemterminálisra, valamint vegyük fel az X a a új szabályokat. Formálisan,

H ''={Aa|aT, AaH}∪{A  → r|Ar '∈H, r '∉T, és h(r ')=r, ahol h az az izomorfizmus, amely N minden eleméhez önmagát, a T elemeihez pedig N t megfelelő elemeit rendeli} ∪{X a a|aT}.

Az így létrejött G ''=(N '', T, S, H '') nyelvtan ekvivalens a G '- vel és szabályaiban a terminális csak A → a alakú szabályban fordul elő.

Ekkor G ''=(N '', T, S, H '') nyelvtanban az összes nem A → a alakú szabályunk A → r alakú (AN, rN ''*∖{λ)}. Tekintsük ezek közül azokat a szabályokat, amelyekben |r|>2. Egy ilyen AB 1 B 2B k (k>2) alakú szabályt helyettesíthetünk az

AB 1 Z 1

Z 1B 2 Z 2

Z k-2B k-1 B k

szabályok halmazával, ahol Z 1, Z 2, …, Z k-2 újonnan bevezetett nemterminálisok. Ezt a helyettesítést minden kettőnél hosszabb jobb oldalú szabályra külön-külön végrehajtva a G '''=(N ''', T, S, H ''') nyelvtanunk ekvivalens az előzővel (így az eredetivel is) és H ''' csak az alábbi háromféle szabályt tartalmazhatja:

(1) A → a,

(2) A → B,

(3) A → B C.

Tehát a G ''' nyelvtanra ki kell küszöbölni a H '''- ből az A → B alakú (úgynevezett lánc-)szabályokat, hasonlóan ahogy a reguláris és lineáris nyelvtanoknál megtettük.

(Lásd pl. erős normálformájú reguláris nyelvtanok.)

Tehát definiáljuk minden AN ''' változóhoz a következő halmazokat:

- U 1(A)={A}

- U i+1(A)=U i (A)∪{BN '''|∃CU i (A)|C  → BH '''}, ha i>1

Ekkor N ''' véges volta miatt létezik olyan minimális k index, hogy U k (A)=U k+j (A), ha j=1, 2, …. Jelöljük minden AN ''' nemterminális jelhez tartozó U k (A)- t U(A)- val. Ekkor U(A) éppen azokat a nemterminálisokat tartalmazza, amelyek levezethetőek az A- ból csupán láncszabályokat felhasználva, vagyis tetszőleges A, BN ''' változókra A* B pontosan akkor, ha BU(A). Ezek után definiáljuk a H '''' szabályhalmazt a következőképpen:

H ''''={Ar | van olyan BN ''', hogy BrH ''', rN, BU(A)}.

Az így kapott G ''''=(N '''', T, S, H '''') nyelvtanra L(G)∖{λ}=L(G ''''), mivel az A → B szabályok alkalmazását az előbbi két csoportba tartozó szabályok alkalmazásával biztosítjuk és fordítva. ∎

A Chomsky normálforma használata esetén a leveztési fa egy bináris fa lesz, minden lépésben vagy a mondatforma hossza nő ( A → B C alakú szabály alkalmazása) vagy egy terminális bevezetésével egy ágon befejeződik a levezetés ( A → a alakú szabály esetén).

7.5. példa - Chomsky normálforma 1.feladat


Adjunk meg a G=({S,A,B},{a,b,c},S,H) nyelvtannal ekvivalens Chomsky-féle normálalakú nyelvtant, ahol
H = { S →  ABaba, A →  B, A →  c, B →  AbA, B →  S }.



Megoldás:
(I.) Első lépésben megadunk egy G
               1 nyelvtant, ami ekvivalens a G nyelvtannal és (terminális) normálalakú.
Ehhez először a G nyelvtan minden olyan xi
               
 terminális betűjéhez, amely szerepel olyan szabályban,
ami nem normálalakú, új Xi
               
 nemterminálist vezetünk be.
Ezután a G
               1 nyelvtan H
               1 szabályhalmazát úgy kapjuk, hogy felvesszük az Xi →  xi
               
 szabályokat, valamint
H szabályhalmaz elemeit átvesszük úgy, hogy a szabályokban az xi
               
 betűk azon előfordulásait,
melyek nem (terminális) normálalakú szabályban szerepelnek, Xi
               
-re cseréljük.
 
Jelen esetben legyenek az új nemterminálisok az Xa
               
 és az Xb
               
, ekkor:
G
               1
               =({S,A,B,Xa,Xb
               
},{a,b,c},S,H
               1), ahol
H
               1
               ={ Xa →  a, Xb →  b, S →  ABXaXbXa, A →  B, A →  c, B →  AXbA, B →  S }

(II.) Második lépésben megadunk egy G
               2 nyelvtant, ami ekvivalens
az eredeti nyelvtannal, normálformájú és nem szerepel benne Y →  Y
               1
               Y
               2
               ...Yn
               
n>2 alakú szabály.
Ehhez a G
               1 nyelvtanból indulunk ki.
H
               1 szabályhalmaz Y →  Y
               1
               Y
               2
               ...Yn
               
n>2 alakú szabályait helyettesítjük új szabályokkal,
a többi szabályt pedig változtatás nélkül átvesszük a H
               2 szabályhalmazba.
Minden Y →  Y
               1
               Y
               2
               ...Yn
               
n>2 alakú szabályhoz
vezessünk be Z
               1
               ,Z
               2
               , ... ,Z
               
                  n-2
 új nemterminálisokat,
úgy, hogy Zi
               
-ből az  Y
               
                  i+1
...Yn
               
 szót tudjuk levezetni:
az összes  Y →  Y
               1
               Y
               2
               ...Yn
               
n>2 alakú szabályt helyettesítsük
a következő szabályokkal:
Y →  Y
               1
               Z
               1
               ,

               Z
               1
                →  Y
               2
               Z
               2
               ,
 .                    
 .                    
 .            
Z
               
                  n-3

                →  Y
               
                  n-2

               Z
               
                  n-2

               ,                    

               Z
               
                  n-2

                →  Y
               
                  n-1

               Yn.
 
Jelen esetben:
G
               2
               =({S,A,B,Xa,Xb,Z
               1
               ,Z
               2
               ,Z
               3
               ,Z
               4},{a,b,c},S,H
               2), ahol
H
               2
               ={ Xa →  a, Xb →  b, S →  AZ
               1
               , Z
               1
                →  BZ
               2
               , Z
               2
                →  XaZ
               3
               , Z
               3
                →  XbXa, A →  B, A →  c, B →  AZ
               4
               ,
Z

               4
                →  XbA, B →  S }

(III.) Harmadik lépésben megadjuk az eredeti nyelvtannal ekvivalens
G' Chomsky-féle normálalakú nyelvtant. Ehhez két lépésre van szükség.
Első lépésben meghatározunk egy U(Z) halmazt minden olyan Z nemterminálishoz, mely levezethető
legalább egy másik nemterminálisból a G
               2 nyelvtanban és
szerepel olyan H
               2 halmazban lévő szabály bal oldalán, amelynek jobb oldalán egy terminális
vagy pedig két nemterminális betű áll.
Az U(Z) halmaz tartalmazni fogja az összes olyan nemterminálist,
melyből egy vagy több lépésben levezethető a Z betű.
 
Jelen esetben:
U(B)={A},

               U(S)={B,A}.
Második lépésben a H' szabályhalmazba átvesszük a H
               2 szabályhalmaz mindazon szabályait,
melyek jobb oldalán egy terminális betű vagy pedig kettő nemterminális található,
majd hozzávesszük mindazon szabályokat, melyeket úgy kapunk, hogy a már
átvett szabályok bal oldalán szereplő betűt a hozzá tartozó U halmaz elemeivel helyettesítjük.
 
Formálisan:
H'=(H
               2∪{Z →  p | X →  p∈ H
               2
               ,Z U(X)})∖{X →  Y | X,Y∈ N}.Jelen esetben:
G'=({S,A,B,Xa,Xb,Z
               1
               ,Z
               2
               ,Z
               3
               ,Z
               4},{a,b,c},S,H'), ahol
H'={ Xa →  a, Xb →  b, S →  AZ
               1
               ,B →  AZ
               1
               , A →  AZ
               1
               , Z
               1
                →  BZ
               2
               , Z
               2
                →  XaZ
               3
               , Z
               3
                →  XbXa, A →  c,

               B →  AZ
               4
               , A →  AZ
               4
               , Z
               4
                →  XbA } ★
 

7.6. példa - Chomsky normálforma 2.feladat


Adjunk meg a G=({S,A,B},{x,y,z},S,H) nyelvtannal ekvivalens Chomsky-féle normálalakú nyelvtant, ahol
H={ S → BB, A → S, A → xxzz, A → y, B → AxzxA, B → A }.

                        
Megoldás:
(I.)
Legyenek az új nemterminálisok az X és a Z, ekkor:
G
                  1
                  =({S,A,B,X,Z},{x,y,z},S,H
                  1), ahol
H
                  1
                  ={ X → x, Z → z, S → BB, A → S, A → XXZZ, A → y, B → AXZXA, B → A }
(II.)
G
                  2
                  =({S,A,B,X,Z,Z
                  1
                  ,Z
                  2
                  ,Z
                  3
                  ,Z
                  4
                  ,Z
                  5},{x,y,z},S,H
                  2), ahol
H
                  2
                  ={ X → x, Z → z, S → BB, A → S, A → XZ
                  1
                  , Z
                  1
                   → XZ
                  2
                  , Z
                  2
                   → ZZ, A → y, B → AZ
                  3,
Z
                  3
                   → XZ
                  4
                  , Z
                  4
                   → ZZ
                  5
                  , Z
                  5
                   → XA, B → A }
(III.)
U(S)={A,B},U(A)={B}.

                  G'=({S,A,B,X,Z,Z
                  1
                  ,Z
                  2
                  ,Z
                  3
                  ,Z
                  4
                  ,Z
                  5},{x,y,z},S,H'), ahol
H'={ X → x, Z → z, S → BB, A → BB, B → BB, A → XZ
                  1
                  , B → XZ
                  1
                  , Z
                  1
                   → XZ
                  2
                  , Z
                  2
                   → ZZ,

                  A → y, B → y, B → AZ
                  3
                  , Z
                  3
                   → XZ
                  4
                  , Z
                  4
                   → ZZ
                  5
                  , Z
                  5
                   → XA } ★
 


7.7. példa - Chomsky normálforma 3.feladat


Adjunk meg a G=({S,A,B},{x,y},S,H) nyelvtannal ekvivalens Chomsky-féle normálalakú nyelvtant, ahol
H={ S → ABBAB, S → x, A → BB, A → S, A → B, B → ASA, B → y }.                    


Megoldás:           
(I.) Mivel a G nyelvtan már normálalakban van, ezért G
                  1
                  =G.
(II.)
G
                  2
                  =({S,A,B,Z
                  1
                  ,Z
                  2
                  ,Z
                  3
                  ,Z
                  4},{x,y},S,H
                  2), ahol
H
                  2
                  ={ S → AZ
                  1
                  , Z
                  1
                   → BZ
                  2
                  , Z
                  2
                   → BZ
                  3
                  , Z
                  3
                   → AB, S → x, A → BB, A → S, A → B,

                  B → AZ
                  4
                  , Z
                  4
                   → SA, B → y }
(III.)
U(S)={A},U(B)={A}.

                  G'=({S,A,B,Z
                  1
                  ,Z
                  2
                  ,Z
                  3
                  ,Z
                  4},{x,y},S,H'), ahol
H'={ S → AZ
                  1
                  , A → AZ
                  1
                  , Z
                  1
                   → BZ
                  2
                  , Z
                  2
                   → BZ
                  3
                  , Z
                  3
                   → AB, S → x, A → x, A → BB, B → AZ
                  4,
A → AZ
                  4
                  , Z
                  4
                   → SA, B → y, A → y } ★


7.3.2. Greibach normálforma

A Chomsky-féle normálforma segítségével kiküszöböltük a levezetésekből az A* A alakú formákat, amelyek a levezetés hosszát a végtelenségig megnövelhették kellő odafigyelés hiányában. Egy másik féle probléma merülhet fel A → A B alakú szabály használata során: ha legbaloldalibb módon szeretnénk a keresett szót levezetni, és pont egy ilyen alakú szabály alkalmazható, akkor ugyanígy alkalmazható lesz a következő mondatformára, majd az azt követőre, és így tovább. Ha a levezetés során mást nem veszünk figyelembe, akkor itt a levezetési fa felépítésével egy végtelen ágba kerültünk így a visszalépéses kereső algoritmusa nem alkalmazható a szóprobléma megoldására.

Balrekurziónak nevezzük, ha egy G=(N, T, S, H) nyelvtanban van olyan AN, hogy A* A r (valamely r∈(NT)+ esetén). Közvetlen balrekurzióról beszélünk, ha AA r vagyis van olyan szabály, hogy A → A r.

A közvetlen balrekurzió megszüntetésére szolgáló algoritmus lépéseivel analóg módon továbbalakítva a nyelvtant jutunk el a Greibach-féle normálalakig, ami a balrekurzió teljes kiküszöbölésével adódik:

A következő normálforma az amerikai Sheila Greibach nevéhez fűződik.

15. Definíció. Egy környezetfüggetlen nyelvtanról akkor mondjuk, hogy Greibach-féle normálalakú, ha minden szabálya A → a r alakú, ahol AN, aT, rN *. ★

Igaz a következő tétel, aminek bizonyítását most nem közöljük, de a konstruktív algoritmust egy példán bemutatjuk.

47. Tétel. Minden környezetfüggetlen nyelvtanhoz van vele ekvivalens Greibach normálformájú nyelvtan.

Az eredmény jelentősége az, hogy a környezetfüggetlen nyelvek is generálhatóak (a reguláris és a lineáris nyelvekhez hasonlóan) oly módon, hogy a levezetés minden lépésében történik terminális bevezetése. Ennek következtében a levezetés lépésszáma pontosan annyi kell hogy legyen, mint a levezetendő szó hossza.

7.8. példa - Greibach normálforma 1.feladat


Adjunk meg a G({A,B,C},{0,1},S,H) nyelvtannal ekvivalens Greibach normálformájú nyelvtant, ahol
H={
S → BC,

                  B → CS,

                  B → 1,

                  C → SB,

                  C → 0}         



Megoldás:           
(I.) A balrekurzió kiiktatása

Állítsunk fel egy sorrendet a nemterminálisok közt. Legyen ez most S < B < C !
Alakítsuk át a szabályokat úgy, hogy a sorrendben később következő szabályból ne legyen levezethető
olyan szó, melynek első betűje egy sorrendben előrébb lévő nemterminális (és haladjunk a választott
sorrendben: tekintsük először az A →  u alakú szabályokat... (u ∈ (N ∪ T)+):
S →  BC  maradhat (S < B),
B →  CS  maradhat (B < C),
B →  1   maradhat.

C →  SB helyett C →  BCB, mert (C > S miatt, mintha a C ⇒SB ⇒BCB levezetésben már az
S -re is alkalmaztunk volna szabályt.)
majd C → BCB helyett C → CSCB és C → 1CB ( C > B miatt, mintha a BCB első B -jére is
alkalmaztunk volna már levezetési szabályt.)

C →  0 maradhat.

(II.) A közvetlen balrekurzió kiiktatása

S → BC,
B → CS,
B → 1,
C → CSCB,
C → 1CB,
C → 0.

Csak a C → CSCB szabály tartalmaz közvetlen balrekurziót.
Csoportosítjuk a C → u (u ∈ (N ∪ T)+) alakú szabályokat az alapján, hogy balrekurzívak, vagy nem.
Megjegyezzük, hogy egyik csoport sem lehet üres, ha rekurzió előfordul és a C nem felesleges
szimbóluma a nyelvtannak.
 
Vezessük be a C' új nemterminálist, mely a sorrendben előzze meg a már létezőeket!
A sorrend tehát C' < S < B < C legyen!

A balrekurzív C → CSCB szabály helyett vegyük fel a következőket:

C → 0C',
C → 1CBC',
(a nem balrekurzív szabályokat vegyük fel úgy is, hogy az új C' szimbólum szerepel a jobboldal végén)
C' → SCB,
C' → SCBC'.
(Az új nemterminálissal a baloldalon vegyük fel a balrekurzív szabály(ok) jobb oldalát a balrekurziót
okozó kezdő C nélkül. Vegyük fel ezeket a szabály(oka)t úgy is, hogy a jobboldal végén a C' is szerepel.)

Így a szabályok:
S → BC,
B → CS,
B → 1,
C → 1CB,
C → 0,
C → 0C',
C → 1CBC',
C' → SCB,
C' → SCBC'.

(III.) Ha a jobboldal első betűje nemterminális, akkor helyette a belőle levezethető jobboldalakat kell
behelyettesíteni:

C → 1CB ;
C → 0 ;
C → 0C' ;
C → 1CBC';    megfelelő szabályok

B → 1 ;
B → CS helyett B → 1CBS, B → 0S, B → 0C'S, B → 1CBC'S; (vagyis a C helyett az előző négy
szabály jobboldalait)

S → BC helyett S → 1C, S → 1CBSC, S → 0SC, S → 0C'SC, S → 1CBC'SC; (vagyis a B helyett
az előző öt szabály jobboldalait)

C' → SCB helyett C' → 1CCB, C' → 0SCCB, C' → 1CBSCCB, C' → 1CBC'SCCB, C' → 0C'SCCB ;
C' → SCBC' helyett C' → 1CCBC', C' → 0SCCBC', C' → 1CBSCCBC', C' → 1CBC'SCCBC',
 C' → 0C'SCCBC'

Ezzel nyelvtanunk megfelelő formájú lett.
G=({S,B,C,C'},{0,1},S,H'), ahol H' szabályai:{
C → 1CB,
C →  0,
C → 0C',
C → 1CBC',
B →  1,
B → 1CBS,
B → 0S,
B → 0C'S,
B → 1CBC'S,
S →  1C,
S → 0SC,
S → 1CBSC,
S → 1CBC'SC,
S → 0C'SC,
C' → 1CCB,
C' → 0SCCB,
C' → 1CBSCCB,
C' → 1CBC'SCCB,
C' → 0C'SCCB,
C' → 1CCBC',
C' → 0SCCBC',
C' → 1CBSCCBC',
C' → 1bCBC'SCCBC',
C' → 0C'SCCBC'
}
Ha ezek a szabályok a jobboldali első terminális után még tartalmaznának terminálist,
akkor azt már csak a normális alakra hozásnál tanult módon, új nemterminálisok bevezetésével
kellene kiiktatni. ★