3.2. Generatív nyelvtan, Chomsky-féle nyelvosztályok

Egy W=(V, A x, H) generatív rendszerből úgy kapunk generatív nyelvtant, ha a V ábécét felbontjuk közös elemet nem tartalmazó nem üres (és V végessége miatt véges) N és T részhalmazokra ( V=NT, NT=∅, N≠∅, T≠∅), az A x pedig egyetlen, egybetűs, N- beli (általában S- el jelölt) elemből áll, s minden H- beli szabály baloldala legalább egy N- beli betűt tartalmaz. Formálisan tehát a generatív grammatika (vagy generatív nyelvan) definíciója:

1. Definíció. A G=(N, T, S, H) rendezett négyest generatív nyelvtannak (vagy generatív grammatikának) nevezzük, ha N és T diszjunkt véges ábécék, SN, H⊂(NT)* N(NT)*×(NT)*. Az N elemeit nemterminális jeleknek vagy változó szimbólumoknak nevezzük, és általában nagybetűkkel (S, A, B, C, …) jelöljük. A T elemeit terminális jeleknek, vagy konstansoknak nevezzük, és általában kisbetűkkel (a, b, c, …) jelöljük. A H elemeit képező (p, q) rendezett párokat (mint korábban is) helyettesítési szabályoknak nevezzük, és általában p → q alakban írjuk. Az S egy kitüntetett nemterminális jel, amely a G nyelvtanban a generálás kiinduló vagy kezdő eleme, másnéven mondatszimbóluma (startszava). ★

Most definiáljuk, hogy hogyan állítunk elő egy nyelvet egy generatív nyelvtan segítségével, először most is (közvetlen) levezethetőséget kell definiálnunk, ez tulajdonképpen megegyezik a generatív rendszerekben meghatározott azonos fogalmakkal:

2. Definíció. Egy G generatív nyelvtanban az r∈(NT)* szóból egy lépésben, vagy közvetlenül levezethető a t∈(NT)* szó, ha van olyan p → q helyettesítési szabály a H- ban és p 1, p 2∈(NT)* úgy, hogy r=p 1 p p 2 és t=p 1 q p 2. Jelölés: r G t, vagy ha egyértelműen meghatározható a G, akkor rt.

Egy G generatív nyelvtanban az r szóból levezethető a t szó, ha van olyan r 0, r 1, …, r n véges szósorozat a (NT)*- ban, amelyre teljesül, hogy r 0=r, r n =t és r i r i+1 (i=0, 1, …, n-1). Ezt a relációt r* t- vel jelöljük. Megegyezés szerint minden r∈(NT)* szóra r* r teljesül.

A G=(N, T, S, H) generatív nyelvtan által generált nyelven a T *- beli szavak következő halmazát értjük: L(G)={w|S* w, wT *}. ★

Úgy is mondhattuk volna, hogy L(G)=L g (G)∩T *, ahol L g (G) a G mint generatív rendszer, pontosabban a (V, {S}, H) generatív rendszer által generált nyelvet jelöli. (Tehát vigyázat: Nem tévesztendő össze a G generatív nyelvtan és a G mint generatív rendszer által generált nyelv, hiszen L(G)⊆L g (G), vagyis a két nyelv nem esik egybe: SL g (G), de SL(G) !) L g (G) elemeit, vagyis azon (NT) feletti szavakat amelyek az S modatszimbólumból levezethetőek, mondatformáknak, N * elemeit nemterminális szavaknak, T * elemeit pedig terminális szavaknak, vagy a nyelvtani analógia miatt mondatoknak is hívjuk. Egy adott nyelvtan esetén a levezetés során mondatformák szereplenek, így a levezetett terminális szót sokszor egyszerűen csak levezetett szónak fogjuk hívni (amennyiben ez nem zavaró).

Chomsky nyelvészként a természetes nyelvek leírását szerette volna elérni generatív nyelvtanok segítségével, így a fogalom megfelel annak, hogy a változók a nyelvi fogalmak (ige, főnév, stb.), a konstansok pedig a szótári szavak elemeinek absztrakciói. Habár a természetes nyelvek teljes formális leírása ilyen formán a mai napig nem született meg, a generatív nyelvtanok szerepe igen fontossá vált a mesterséges nyelvek, így a számítógépek fejlődésével, pl. a programnyelvek formális leírásakor.

Első példánkban kezdetleges számítógépes nyelvészeti leírással próbálkozunk.

3.19. példa - Generatív nyelvtan természetes nyelv "leírására"

Legyen G=(N, T, S, H), ahol N={S, (i g e), (f ő n é v), (m e l l é k n é v)}, T={ magyar ábécé betűi }, H={S → (i g e), (i g e) → (f ő n é v)(i g e), (f ő n é v) → (m e l l é k n é v)(f ő n é v), (m e l l é k n é v)  → a z (m e l l é k n é v), (i g e) → t a n u l, (f ő n é v) → d i á k, (m e l l é k n é v) → e n g e d e l m e s}.


Tekintsük a következő levezetést.

S⇒(i g e)⇒(f ő n é v)(i g e)⇒(m e l l é k n é v)(f ő n é v)(i g e)⇒a z (m e l l é k n é v)(f ő n é v)(i g e)

a z e n g e d e l m e s (f ő n é v)(i g e)⇒a z e n g e d e l m e s d i á k (i g e)⇒a z e n g e d e l m e s d i á k t a n u l.

Ugyanígy levezethető "nyelvtanunkkal" például: a z a z e n g e d e l m e s d i á k t a n u l, stb. ★

A generatív nyelvtan persze nemcsak nyelvtani elemzésre alkalmas eszköz. Mint a következő (M. Soittola -tól, illetve M. Penttonen-től származó) példák is mutatják, segítségével elő tudjuk állítani az összes négyzetszámot, illetve a prímszámokat.

3.20. példa - Unáris négyzetszámok

G=({S, X, Y, Z, X 1, X 2, Y 1, Y 2}, {a}, S, {Sa, Sa X X 2 Z, X 2 Za a, X aa a, Y aa a, X 2 ZY 1 Y X Z, X X 1X 1 Y X, Y X 1Y 1 Y X, X Y 1X 1 Y, Y Y 1Y 1 Y, a X 1a X X Y X 2, X 2 YX Y 2, Y 2 YY Y 2, Y 2 XY X 2}.


Az összes négyzetszámot a következőképp állíthatjuk elő:

Először bizonyítsuk be hogy a generált terminális szavak hossza eleme lesz az 1, 1+3, 1+3+5, …, 1+3+…+(2n-1), … sorozatnak:

Csoportosítsuk a szabályokat az alábbi módon.

(1) S → a, Sa X X 2 Z,

(2) X 2 Za a,

(3) X aa a, Y aa a,

(4) X 2 ZY 1 Y X Z,

(5) X X 1X 1 Y X, Y X 1Y 1 Y X,

(6) X Y 1X 1 Y, Y Y 1Y 1 Y,

(7) a X 1a X X Y X 2,

(8) X 2 YX Y 2, Y 2 YY Y 2, Y 2 XY X 2.

A továbbiakban (1)-(8) a megfelelő csoport valamelyik szabályát jelöli. (1) (mely a mondatszimbólumból kiinduló szabályokat mutatja) az a és a X X 2 Z szavak valamelyikét eredményezi. Tekintsünk a p i =a X q i X 2 Z, q i ∈{X, Y}* szóból terminális szavakhoz vezető levezetéseket. Először csak (2) vagy (4) alkalmazható. Ha (2) került alkalmazásra, akkor a folytatás egyedüli módja (3) alkalmazása egész addig, míg egy 1+3+|q i | hosszú terminális szót nem kapunk. (Mivel a terminális ábécé egy betűből áll, minden szó meg van határozva a hossza által.) Ha (4) kerül alkalmazásra, az a X q i Y 1 Y X Z szót kapjuk. A folytatás egyedüli módja az "1" index balra léptetése (5)- el és (6) egész addig, amíg (7) alkalmazhatóvá válik. (7) alkalmazása után egy a X X Y X 2 q' i Y Y X Z szóhoz jutunk, ahol q' i - t úgy kapjuk q i - ból, hogy X minden előfordulásakor Y- t írunk. A "2" index jobbra léptetésének egyedüli lehetősége a (8), mely a P i+1=a X Q i+1 X 2 Z, Q i+1=X Y Q' i Y Y szavakhoz vezet. (Megjegyezzük, hogy (8) eleget tesz a "2" index jobbra léptetési követelményének, hisz X 2 XX X 2 nem szükséges, mivel nem fordul elő két egymást követő X.) Egy, a kiinduló p i szavunkkal megegyező formájú szóhoz jutottunk, s kezdődhet egy új ciklus (2) vagy (4) alkalmazásával. Következésképp, |q i+1|=|q i |+q i [X]+5, ahol q i [X] jelöli az X betű előfordulásainak számát q i - ben. Mivel világos, hogy q i+1[X]=q i [X]+2, kapjuk, hogy a generált terminális szavak hosszai elemei az 1, 1+3, 1+3+5, …, 1+3+…+(2n-1), … sorozatnak.

Másrészt könnyen igazolható, és közismert, hogy n 2=1+3+…+(2n-1)(n=1, 2, …). Így L(G)={a n 2 |n=1, 2, …}. ★

3.21. példa - Unáris prímszámok

G=({S, A, B, C, D, E, X 1, X 2, X 3, Y A , Y B , Y 1, Y 2, Y 3, Y 4, Y 5, Y 6, Y 7, Y 8, Y 9}, {a}, S, {Sa 2, S  → a 3, Sa 5, S  → a 7, SY 1 A 6 X 3, Y 1Y 1 A 2, Y 1 A 3X 1 A 3 X 2, i A X 2 AD Y 2 Y i E, i D Y 2D Y 2 i, X 1 D Y 2X 1 B Y 3, Y 3 ii Y 3, Y 3 Y i EY i Y 3 E, Y 3 E ii Y 3 E, Y 3 E X 3Y 4 C X 3, i Y 4Y 4 i, Y i Y 4  → i X 2, (i∈{A, B}), X 1 BX 1 Y 5, Y 5 BB Y 5, Y 5 X 2 AY 6 X 2 A, B Y 6Y 6 A, X Y 6X 1 A, C X 3Y 7 X 3, C Y 7Y 7 A, B A j X 2 Y 7Y 8 A j+1 X 2, (j∈{0, 1, 2}), A 4 X 2 Y 7Y 8 A 4 X 2, A Y 8Y 8 A, B Y 8Y 8 A, X 1 Y 8  → X 1 A, X 2 X 3  → Y 9 a, A Y 9Y 9 a, X 1 Y 9  → a a}). Igazolható hogy L(G)={a p |p -p r í m s z á m}.


Az összes prímszámot a következőképp állíthatjuk elő: Csoportosítsuk a szabályokat a következő módon.

(1) Sa 2, S  → a 3, S  → a 5, S  → a 7,

(2) SY 1 A 6 X 3, Y 1Y 1 A 2, Y 1 A 3X 1 A 3 X 2,

(3) i A X 2 AD Y 2 Y i E, i D Y 2D Y 2 i, X 1 D Y 2X 1 B Y 3, Y 3 ii Y 3, Y 3 Y i EY i Y 3 E, Y 3 E ii Y 3 E, Y 3 E X 3Y 4 C X 3, i Y 4Y 4 i, Y i Y 4  → i X 2, i∈{A, B},

(4) X 1 BX 1 Y 5, Y 5 BB Y 5, Y 5 X 2 AY 6 X 2 A, B Y 6Y 6 A, X Y 6X 1 A,

(5) C X 3Y 7 X 3, C Y 7Y 7 A, B A j X 2 Y 7Y 8 A j+1 X 2, A 4 X 2 Y 7Y 8 A 4 X 2, A Y 8Y 8 A, B Y 8Y 8 A, X 1 Y 8  → X 1 A, j∈{0, 1, 2}

(6) X 2 X 3  → Y 9 a, A Y 9Y 9 a, X 1 Y 9  → a a.

Az (1)- beli szabályok generálják minden 10 alatti prím n- re az a n alakú terminális szavakat. A (2)- beli szabályok generálják minden 9- nél nem kisebb n- re az X 1 A 3 X 2 A n-6 X 3 alakú szavakat. A (3)-(5) szabályok tesztelik, hogy n osztható-e 3- al, s ha nem, akkor eljutunk az X 1 A 4 X 2 A n-7 X 3 szóhoz. Ezután következik a 4- el oszthatóság tesztje. Negatív eredmény esetén X 2 egyet lép jobbra. A pozitív válasz olyan levezetést eredményez, mely nem vezet terminális szóhoz. Ha az oszthatósági teszt eredménytelen, eljutunk az X 1 A n-3 X 2 X 3 szóhoz, s (6) válik alkalmazhatóvá, mely elvezet a n - hez. A részletesebb bizonyítást mellőzzük. ★

A generatív nyelvtan duális fogalma az analitikus nyelvtan, amit a generatív nyelvtanhoz hasonlóan, G=(N, T, S, H) alakban adunk meg, benne N a változó(szimbólumo)k, vagy még más néven, a nemterminálisok halmaza, T a konstansok vagy terminálisok halmaza, S a mondatszimbólum, H pedig (mint korábban) a szabályok halmaza. E fogalomnál is használjuk a V=NT jelölést , N * elemeit nemterminális szavaknak, T * elemeit pedig terminális szavaknak, vagy a nyelvtani analógia miatt mondatoknak hívjuk (ugyanúgy mint a generatív nyelvtannál). Szemben a generatív nyelvtannal, itt azt tételezzük fel, hogy minden H- beli szabály jobboldala legalább egy N- beli betűt tartalmaz. A G analitikus nyelvtan által acceptált, vagy elfogadott, vagy még más néven, felismert nyelven a T *- beli szavak következő halmazát értjük: L(G)={wT *|w G * S}. Itt is mondhattuk volna, hogy L(G)=L a (G)∩T *, ahol L a (G) a G mint analitikus rendszer, pontosabban az (NT, {S}, H) analitikus rendszer által felismert nyelvet jelöli. (Tehát vigyázat: Hasonlóan a generatív változatokhoz, nem tévesztendő össze a G analitikus nyelvtan és a G mint analitikus rendszer által felismert nyelv, hiszen L(G)⊊L a (G), vagyis a két nyelv soha nem esik egybe!)

Érvényes a következő tétel, melynek bizonyítását az olvasóra bízzuk.

1. Tétel. Tekintsünk egy tetszőleges G=(N, T, S, H) tetszőleges generatív (analitikus) nyelvtant. Alkossuk meg hozzá az összes olyan q → p szabályok H ' halmazát, melyekre p → qH. Ekkor a G '=(N, T, S, H ') analitikus (generatív) nyelvtanra L(G ')=L(G).

3.22. példa - Gyakorló feladat

Az 1. Tétel. felhasználásával, továbbá az előző két példa segítségével készítsünk analitikus nyelvtanokat, melyek által felismert nyelvek L(G)={a n 2 |n=1, 2, …}, illetve L(G)={a p |p - prímszám }. ★


A 1. Tétel. alapján minden (generatív vagy analitikus) nyelvtan befoglalható egy vele ekvivalens duális nyelvtannal alkotott párba. (Nevezetesen, minden generatív nyelvtanhoz tartozik egy vele ekvivalens analitikus nyelvtan, s megfordítva, minden analitikus nyelvtanhoz tartozik egy vele ekvivalens generatív nyelvtan.) A továbbiakban a "nyelvtan" elnevezést fenntartjuk a "generatív nyelvtan" elnevezés rövidítésére. Nyelvtan alatt tehát mindig generatív nyelvtant fogunk érteni (míg analitikus nyelvtan esetén mindig kitesszük az "analitikus" jelzőt).

3.2.1. Chomsky-féle nyelvosztályok

A nyelvtan és az általa generált nyelv definíciója szerint minden nyelvtanhoz egy egyértelműen meghatározott nyelv tartozik, de megfordítva, egy nyelvet nem csak egy nyelvtannal generálhatunk.

Két nyelvtant (gyengén) ekvivalensnek nevezünk, ha ugyanazt a nyelvet generálják, vagy az általuk generált nyelv legfeljebb az üresszóban tér el. Tehát, formálisan, G 1 és G 2 (gyengén) ekvivalens, ha L(G 1)∖{λ}=L(G 2)∖{λ}.

Az ekvivalencia fogalmának ismeretében kézenfekvőnek látszik a különböző nyelvtanokat bizonyos formai tulajdonságok alapján osztályokba sorolni. Az osztályozás alapját a helyettesítési szabályok alakjára vonatkozó megszorítások képezik abban a hierarchiában, amelyet az elmélet egyik megalapozója, N. Chomsky vezetett be, és amelyet alább ismertetünk.

3. Definíció. A G=(N, T, S, H)- t i -típusú nyelvtannak (i=0,1,2,3) nevezzük, ha az alábbi megszorítások közül az i- edik teljesül:

(0) Mondatszerkezetű nyelvtan, (Phrase-structure). A generatív nyelvtan korábban már ismertetett általános definíciójánál feltettük, hogy H olyan (NT)*- beli párokból áll, melyek első eleme (azaz a szabály baloldala) tartalmaz legalább egy nemterminálist. H- ra ebben az esetben (azaz i=0 esetén) ezen kívül nem rovunk ki külön feltételt.

(1a) Szóhossznemcsökkentő, vagy monoton nyelvtan, (Monotone). Minden H- beli p → q szabályra |p| ≤ |q| teljesül, vagy S → λ alakú, de ez esetben, vagyis SλH előfordulása esetén S nem lép fel egyetlen H- beli szabály jobboldalán sem.

(1) Környezetfüggő nyelvtan, (Context-Sensitive). Minden H- beli szabály vagy p 1 A p 2p 1 q p 2 alakú, aholis p 1, p 2∈(NT)*, AN, q∈(NT)+, (emlékeztetőül: (NT)+=(NT)*∖{λ}) vagy pedig S → λ alakú. Utóbbi esetben, azaz SλH előfordulása esetén S nem lép fel egyetlen H- beli szabály jobboldalán sem.

(2) Környezetfüggetlen nyelvtan, (Context-Free). Minden H- beli szabály A → p alakú, aholis AN, p∈(NT)*.

(2.5) Lineáris nyelvtan, (Linear). Minden H- beli szabály Au B v vagy A → u alakú, ahol A, BN, u, vT *.

(3) Reguláris nyelvtan, (Regular). Minden H- beli szabály vagy A → u B, vagy pedig A → u alakú, ahol A, BN, uT *. ★

A 0-típusú nyelvtanokat mondatszerkezetű nyelvtanoknak is szokás nevezni, utalva azok nyelvészeti eredetére. Az 1a-típusnál a monoton, illetve szóhossznemcsökkentő név önmagáért beszél, itt a levezetés során nem csökkenhet a mondatforma hossza (az egyedüli Sλ lehetséges levezetést kivéve). Az 1-típusúakat környezetfüggőnek nevezzük, az elnevezés itt arra mutat, hogy egy szabály egyetlen A nemterminális helyébe egy nem üresszónak a beírását jelenti, de csak akkor ha a nemterminális közvetlen környezete egy adott p 1, p 2 szópár. (Természetesen megengedett az is, hogy p 1, p 2 bármelyike, vagy akár mind a kettő üres legyen.) Üres szavat csakis a mondatszimbólum helyébe tehetünk, s azt is csak egy levezetés legelső lépésében teszi lehetővé az 1-típusú nyelvtan. Ezt biztosítjuk azon megszorítással, hogy ha egy 1-típusú nyelvtanban egy p 1 A p 2p 1 q p 2 szabályban q=λ csak úgy lehessen, ha A=S, p 1=p 2=λ (azaz S → λ szabályról van szó). S hogy egy levezetés során az S helyébe csak az első lépésben lehessen üresszót tenni (a többi nemterminálisra ez a lehetőség is ki van zárva), az S → λ szabály előfordulása esetén kizárjuk annak lehetőségét, hogy S szabályok jobboldalán szerepeljen. Utalva arra, hogy a 2-típusú nyelvtanok esetén egy szabály baloldalán álló nemterminális bármilyen környezetben helyettesíthető a szabály jobboldalán álló szóval, ezesetben környezetfüggetlen nyelvtanokról beszélünk. Ez nem áll szemben a környezetfüggéssel, hiszen ott az üresszó, mint környezet is megengedett, mint látni fogjuk inkább arról van szó, hogy a környezetfüggetlen nyelvtanok a környezetfüggőknek speciális esetei. Ha egy 2-típusú nyelvtan minden szabálya legfeljebb egy nemterminálist tartalmaz a jobb oldalán, akkor eljutunk a lineáris grammatika fogalmához. A lineáris nyelvtanok, mint látni fogjuk, a hierarchiában a 2- és a 3-típus között helyezkednek el. Ha egy lineáris nyelvtanban speciálisan az összes Au B v alakú szabályban v=λ, akkor 3-típusú nyelvtanhoz jutunk, amik a jobb-lineáris nyelvtan elnevezést innen kapták. Hasonló módon, ha az összes Au B v alakú szabályban u=λ, akkor bal-lineáris nyelvtanokról beszélünk.

4. Definíció. Egy nyelvről azt mondjuk, hogy mondatszerkezetű (RE) / monoton / környezetfüggő (CS) / környezetfüggetlen (CF) / lineáris (LIN) / jobblineáris / ballineáris / reguláris (REG), ha mondatszerkezetű / monoton / környezetfüggő / környezetfüggetlen / lineáris / jobblineáris / ballineáris / reguláris nyelvtannal generálható. Továbbá az i=0, 1, 2, 3 értékek esetén azt mondjuk, hogy egy nyelv i-típusú, ha van olyan i-típusú nyelvtan, amely azt generálja. ★

Egyszerűen bizonyíthatók a következő tételek.

2. Tétel. Minden G i-típusú (i=0,1,2,3) nyelvtanhoz létezik egy vele ekvivalens G ' i-típusú nyelvtan, amelynek szabályai jobb oldalán a mondatszimbólum nem lép fel.

Bizonyítás. Valóban, ha G=(N, T, S, H) i-típusú nyelvtan, akkor egy ilyen G ' nyelvtant megadhatunk G '=(N∪{S '}, T, S ', H ') alakban, ahol S '∉N és H '=H∪{S '  → p|SpH}. ∎

3. Tétel. Ha az L nyelv i-típusú, akkor L∪{λ} is.

Bizonyítás. Legyen G=(N, T, S, H) egy i-típusú nyelvtan melyre L=L(G) és melyben az előző tétel értelmében a mondatszimbólum nem fordul elő egyik szabály jobboldalán sem. Ha L tartalmazza az üresszót, L∪{λ}=L i-típusú volta automatikusan teljesül. Ha nem tartalmazza, akkor tekintsünk egy G ' nyelvtant, ahol G '=(N, T, S, H ') és H '=H∪{S  → λ}. Ekkor a G ' i-típusú nyelvtan generálja L∪{λ}-t. ∎

3.23. példa - Grammatikák főbb típusai 1. példa


Az alábbi szabályok hányas típusú grammatika elemei lehetnek, ha a kisbetűk terminálist,
a nagybetűk nemterminálist jelölnek?



                  A → B
3-as típusú: ez a szabály X → xY alakú, A=XN és x=λT*
                  
, és Y=BN.
2-es típusú: X → p alakú, X=ANp=BV*
                  
.
1-es típusú: P
                  1
                  PP
                  2
                   →  P
                  1
                  QP
                  2
                   alakú, ahol P
                  1
                  =P
                  2
                  V*, P=AN, Q=BV+
                  

0-ás típusú, ahol a szabályokra nincs megkötés azon túl, hogy minden szabály baloldala tartalmaz
nemterminálist.
(ha nemcsak a 0,1,2,3 típusokat vizsgáljuk, akkor lineáris és monoton is)

A → BC
2-es típusú X → p alakú, X=AN, és p=BCV*
                  
.
1-es típusú: P
                  1
                  PP
                  2
                   →  P
                  1
                  QP
                  2
                   alakú, ahol P
                  1
                  =P
                  2
                  V*
                  
P=AN, Q=BCV+
                  
.
0-ás típusú, ahol a szabályokra nincs megkötés azon túl, hogy minden szabály baloldala tartalmaz
nemterminálist.

XY → XaB
1-es típusú, P
                  1
                  PP
                  2
                   →  P
                  1
                  QP
                  2
                   alakú, ahol P
                  1
                  =XV*, P=YN, Q=aBV+, P
                  2
                  V*
                  
.
0-ás típusú, ahol a szabályokra nincs megkötés azon túl, hogy minden szabály baloldala tartalmaz
nemterminálist.


ABC → ACB
0-ás típusú lehet csak, ahol a szabályokra nincs megkötés azon túl, hogy minden szabály baloldala
tartalmaz nemterminálist.
(egyébként, ha nemcsak a 0,1,2,3 típusokat tekintjük, akkor monoton is)

A → λ
3-as típusú: ez a szabály X → x alakú, A=XN és x=λT*
                  
.
2-es típusú: X → p alakú, X=AN, p=λV*
                  
.
0-ás típusú, ahol a szabályokra nincs megkötés azon túl, hogy minden szabály baloldala tartalmaz
nemterminálist.
(ha nemcsak a 0,1,2,3 típusokat tekintjük, akkor lineáris is. Ha A=S (azaz A a mondatszimbólum),
akkor egyéb feltételek teljesülése mellett szerepelhet 1-típusú, vagy monoton nyelvtanban is). ★ 
 


3.24. példa - Grammatikák főbb típusai 2. példa


Milyen típusú a G=({S, A, B},{x, y}, S, H) grammatika, ahol H szabályai:
S → AB, A → BSB,

                  A → BB, B → xAy,

                  B → λ, B → x, B → y.
Megoldás:
S → AB; A → BSB; A → BB; B → xAy megfelel a
0-ás, 1-es és 2-es típusú grammatika követelményeinek, de a 3-asénak nem.
B → x; B → y megfelel a 0-ás, 1-es 2-es és 3-as  grammatika követelményeinek.
B → λ pedig a 0-ás 2-es és 3-as grammatika követelményeinek.
Tehát a grammatikánk minden szabálya megfelel a 0-ás és 2-es típusú grammatika követelményeinek
is. Ilyenkor azt szokták nézni, hogy melyik a legnagyobb index, amelyhez tartozó követelményeinek
a teljes szabályhalmaz eleget tesz. Ez alapján a nyelvtanunk 2-es típusú. ★


3.25. példa - Grammatikák főbb típusai 3. példa


Milyen típusú a következő grammatika?
G=({S, A, B},{a}, S, H), ahol H szabályai a következők:
S → ABa, AB → AaBB,

                  B → aaa, S → AS,

                  AAS → ABS.
Megoldás:
S → ABa (0-ás, 1-es, 2-es)
AB → AaBB (0-ás, 1-es)
B → aaa (0-ás, 1-es, 2-es, 3-as)
S → AS (0-ás, 1-es, 2-es)
AAS → ABS (0-ás, 1-es)
Grammatikánk eleget tesz a 0-ás és az 1-es típus követelményeinek,
ezért a grammatikánk 1-es típusú lesz. ★


3.26. példa - Grammatikák főbb típusai 4. példa


Hányas típusú a következő grammatika?
G=({ S, A, B }, { a, b, c }, S, H), ahol H szabályai a következők:
S → ABc, A → aB,

                  A → Bc, B → aAc,

                  B → bc.
Adjuk meg az összes hatbetűs szót a grammatika által generált nyelvben!
 

Megoldás:
Az összes szabály eleget tesz a 0-ás, 1-es és a 2-es típus követelményeinek,
ezért 2-es típusú a grammatika.

Most határozzuk meg a hatbetűs szavakat!
Először is azt kell megállapítsuk, hogy a grammatika szabályai közül a baloldal mindenhol
rövidebb, mint a jobboldal, vagyis egy szóból sehol sem kapunk rövidebbet (sőt, mindig
szigorúan hosszabb mondatformát kapunk), tehát a levezetéseket elég hatbetűs szavakig nézni,
és azok közül azok lesznek a grammatika által generált nyelvben, melyek csak terminálist
tartalmaznak.
A levezetés első lépése mindenképpen az S → ABc lesz.
Az A helyére vagy Bc vagy aB kerülhet csak.
Mindkét esetben lesz egy négybetűs szavunk, melyben lesz két terminális
és két B nemterminális. B helyére csak bc kerülhet, mert különben úgy kapunk hatbetűs szót,
hogy még marad benne nemterminális.
Ezért a levezetéseink a következők lesznek:
S ⇒ ABc ⇒ aBBc ⇒ abcBc ⇒ abcbcc,
S ⇒ ABc ⇒ BcBc ⇒ bccBc ⇒ bccbcc.
Természetesen van még ezen kívül több levezetés is, de az
csak a nemterminálisok helyettesítésének sorrendjében tér el. ★


3.27. példa - Grammatikák főbb típusai 5. példa

Milyen típusú a G=({S, A, B}, {0, 1}, S, {SAB, A → 0B1, 0B → 011, 1B → 11BS, S → λ})?

Megoldás: A 0B → 011 és 1B → 11BS alakú szabályok miatt csak 1- és 0-típusú lehet. Az S → λ szabály miatt lehetne 1-típusú a nyelvtan, ha S nem szerepelne egyik szabály jobboldalán sem, de mivel 1B → 11BS szabályra ez nem teljesül, a nyelvtan 0-típusú.


3.28. példa - Grammatikák főbb típusai 6. példa

                
Hányas típusú a következő grammatika?
G=({S},{x, y, +, *, ), (}, S, H), ahol H szabályai a következők:
S → S+S, S → S*S, S → (S), S → x, S → y.
Adjunk meg az y*(x+y) szó egy levezetését!


Megoldás:
S → S+S; S → S*S; S → (S) lehetnek 0-ás, 1-es és 2-es típusú szabályok.
S → x; S → y pedig 0-ás, 1-es, 2-es és 3-as típusú szabályok, vagyis minden
szabály eleget tesz a 0-ás 1-es és a 2-es típus követelményeinek, tehát a grammatika 2-es
típusú lesz.

Az y*(x+y) szó egyik levezetése a következő:
S ⇒ S*S ⇒ y*S ⇒ y*(S) ⇒ y*(S+S) ⇒ y*(x+S) ⇒ y*(x+y) ★


3.29. példa - Grammatikák főbb típusai 7. példa


Adott a G=({S,A,B,C },{a,b } ,S, H) nyelvtan, ahol H szabályai:
S → aS, S → baA, A →  aA, A → baaB,
B →  aB, B →  b, B →  baaaC, C →  aC, C →  a.
Milyen típusú? Adjuk meg az aabaabaaabaaaa  szó levezetését!
Megoldás:
A nyelvtan szabályait megnézve, láthatjuk, hogy az összes szabály eleget tesz a 
0-ás, 1-es, 2-es és 3-as típusú nyelvtanok követelményeinek,
tehát a nyelvtan 3-as típusú.

A generálás az első két szabály valamelyikével kezdődhet.
Mivel a keresett szó a-val kezdődik, ezért az 1. szabályt kell használnunk először.
Az első szabály n-szeri (n tetszőleges nem-negatív egész) alkalmazásával anS-et kapunk.
Ahhoz, hogy az S szimbólum eltűnjön a mondatformából a második szabály használatára
van szükség.
Ennek alkalmazása után anbaA-hoz jutunk.
Ezután olyan A-ból kiinduló szabályt kell keresni, ahol a következik a nyíl után. 
Ezért a 3. szabály m-szeri alaklmazásával anbaamA-t kapunk.
Majd a negyedik szabállyal: anbaambaaB-t.
Ezután három alkalmazhatő szabály van.
Az ötödik k-szori alkalmazása az anbaambaaakB alakhoz vezet.
Ekkor a levezetés befejezhető a B →  b szabállyal: anba ambaaakb.
Alternatívaként a B →  baaaC szabállyal folytatható a levezetés: anbaambaaakbaaaC.
Ekkor a C →  aC 
                  j-szeri alkalmazása az anbaambaa akbaaa ajC formához vezet, a levezetés
ekkor az utolsó szabállyal fejezhető be: anbaambaaakbaaaaja eredménnyel.
 


A levezetéseket gráf segítségével is szemléltethetjük. Ebben az esetben az a a b a a b a a a b a a a a szólevezetését a következő fa reprezentálja:

3.30. példa - Grammatikák főbb típusai 8. példa


Adott a G=({ S,A,B }, { a,b }, S, H ) nyelvtan, ahol H={S → a A, A →  Sa,
A →  a, S →  bB, B →  Sb, B →  b, S →  a, S →  b  }.
Milyen típusú? Mely nyelvet generálja?
Adjuk meg az abbabba szó levezetését fa alakban!
Megoldás:
Amint látjuk a szabályok közt van jobb-, illetve bal-lineáris alakú is, ezért a megadott
grammatika nem reguláris. Az viszont minden szabályra teljesül, hogy a nyíl után legfeljebb egy
nemterminális betű szerepel. Tehát a nyelvtan lineáris.
A nyelvtan szabályait csoportokban vizsgálhatjuk.
Az első szabály alkalmazása után a második vagy harmadik szabályt is fel kell használnunk a
levezetésben.
Az első után a harmadik szabállyal a levezetés befejeződik, az S szimbólum helyére aa kerül így a
levezetésben.
Az első és a második szabályok az eredeti S-t aSa-val helyettesítik.
Hasonlóan a következő három szabály az S szimbólumot a bSb, illetve a bb szavakkal helyettesítheti.
Ezek alapján könnyen belátható, hogy a generált szó az elejéről olvasva éppen ugyanaz, mint
a végéről visszafelé olvasva.
Az is látszik, hogy az {a,b} ábécé felett minden ilyen szót előállít a nyelvtanunk.
Az utolsó két szabály a páratlan hosszúságú ilyen tulajdonságú szavak levezetésének
befejezesében játszik szerepet.
Ezt a nyelvet egyébként a kétbetűs ábécé feletti palindrom nyelvnek nevezzük.
Az ábra az abbabba szó levezetési fáját mutatja.
 


3.31. példa - Grammatikák főbb típusai 9. példa


Legyen adott G=({S, A,B,C },{a,b }, S, H) generatív nyelvtan, ahol H={ S → SS, S →  AB,
S → AC, S →  SB, A → a, B →  b}.
Milyen típusú ez a nyelvtan? Mely nyelvet generálja?
Adjuk meg az abaababbaaabbb szó levezetési fáját!
Megoldás:
A nyelvtan környezetfüggetlen.
Az utolsó két szabály alapján az A, illetve a B szimbólumok az a és b terminálisoknak felelnek meg.
A második, illetve a harmadik és negyedik szabályok használata egy-egy A és B szimbólumot vezet
be, mégpedig úgy, hogy az A a B előtt szerepel. A nyelv minden szavában megegyezik tehát az a és b
betűk száma.
Másrészt az is igaz, hogy a nyelv egy szavának minden kezdőszeletében legalább annyi a van, mint
ahány b.
(Ez a nyelv egyébként a kétbetűs ábécé fölötti Dyck-nyelv, vagyis a zárójelek nyelve.
Zárójelei: a a nyitó; b pedig a záró zárójeleket jelenti.)
Az ábra mutatja az abaababbaaabbb szó levezetési fáját.                                
 


3.2.2. A Chomsky hierarchia

Definíció szerint azonnal látható, hogy minden 3-típusú nyelvtan egyben lineáris, és minden lineáris nyelvtan egyben 2-típusú is, valamint minden 1-típusú nyelvtan monoton és minden monoton nyelvtan egyben 0-típusú is. Az is nyilvánvaló, hogy minden 2-típusú, lineáris vagy 3-típusú nyelvtan egyben 0-típusú is. Nézzük meg az 1-típusú és a 2-típusú nyelvtanok közötti kapcsolatot.

4. Tétel. (Üresszó-lemma). Minden környezetfüggetlen G grammatikához megadható olyan G ' környezetfüggetlen nyelvtan, hogy L(G)=L(G ') (azaz az általuk generált nyelv ugyanaz), s ha λL(G), akkor a G '- beli szabályok jobboldalán λ nem fordul elő. Ha viszont λL(G), akkor az egyetlen G '- beli szabály aminek jobboldala az üresszó S ' → λ, ahol S ' a G ' mondatszimbólumát jelöli. Ezesetben, azaz λL(G ') fennállása esetén viszont S ' (azaz a G ' mondatszimbóluma) nem fordulhat elő egyetlen G '- beli szabály jobboldalán sem. Ennek megfelelően, tahát G ' nemcsak környezetfüggetlen, de egyben a környezetfüggő definíciónak is eleget tesz.

Bizonyítás. Legyen G=(N, T, S, H) 2-típusú nyelvtan. Megszerkesztünk hozzá egy G 1=(N, T, S, H 1) grammatikát a következő módon. Definiáljuk az U i halmazokat (i=0,1,...) a következő módon: először az U 1={A|A  → λH}, majd az U i+1=U i ∪{A|A  → pH, pU i *}, i ≥ 1 halmazokat. Mivel U 1U 2⊆…U i ⊆…⊆N, és N véges, azért létezik olyan k, hogy U k =U k+1. Az U i (i=1, 2, …) halmazok konstrukciója alapján ekkor látható, hogy minden m pozitív egészre U k =U k+m . Jelöljük ezt U- val, tehát U=U k . Erre az U- ra ekkor A* λ akkor és csak akkor ha AU (AN), azaz λL(G) akkor és csak akkor ha SU. Tekintsük most azt a G 1=(N, T, S, H 1) grammatikát, amelyre Ap 1H 1 pontosan akkor, ha p 1λ és van olyan ApH, hogy p 1=p, vagy p 1 előállíthtó p- ből úgy, hogy p- ből U- beli elemet vagy elemeket hagyunk el. p- ből tehát egy ilyen p 1 szót úgy származtatunk, hogy alkalmas U- beli (nem feltétlen egymástól páronként különböző) A 1, …, A m nemterminális betűkre és (NT)*- beli q 1, …q m+1 szavakra p=q 1 A 1q m A m q m+1 mellett p 1=q 1q m+1 fennálljon. Ekkor nyilvánvaló, hogy L(G 1)⊆L(G)∖{λ}. De megfordítva, L(G)∖{λ}⊆L(G 1) is fennáll, hisz ha S* p és pλ, akkor fennáll pL(G ') is, mivel a p- nek egy G- beli levezetése esetén minden A → λ alakú szabály alkalmazása helyett vehetjük a megfelelő H 1- beli szabályokat. Így azt kaptuk, hogy L(G)∖{λ}=L(G 1). Ha tehát λL(G), akkor G '- ként G 1- et választhatjuk. Ha pedig λL(G), akkor egy új S ' (∉NT) szimbólumot választva vegyük a G '=(N∪{S '}, T, S ', H 1∪{S '  → S, S ' → λ}) nyelvtant, mely ezesetben nyilvánvalóan eleget tesz a tételbeli tulajdonságoknak, így a tétel bizonyítást nyert. ∎

Láthatjuk tehát, hogy a környezetfüggetlen nyelvek generálhatóak olyan (környezetfüggő) nyelvtanokkal, melyekben minden szabály bal oldalának hossza egy.

A fenti tételünk alapján könnyen látható, a Chomsky-féle nyelvosztályok alábbi hierarchiája:

R E GL I NC FC SR E.

Ez a hierarchia valójában élesebb, de ezt a későbbiekben az adott nyelvosztályok vizsgálatakor fogjuk bizonyítani.

A jegyzet során e hirarchia nyelvosztályait is sorra vesszük, és különböző fontos tulajdonságaikat viszgáljuk, ezeket a problémaköröket ismertetjük a Problémakörök alfejezetben.

3.32. példa - Üresszó-lemma 1. feladat



                  G=({S, A, B},{x, y}, S, H), ahol H a következő szabályokból áll:
S → AB, A → BSB, A → BB, B → xAy,
B → λ, B → x, B → y.

Először nézzük meg, hogy az üresszó benne van-e a G által generált nyelvben!

U 1 :={B} - azok a nemterminálisok, amelyekből λ közvetlenül megkapható.
U 2 :={A,B} - azok a nemterminálisok, amelyekből U 1 * -beli szavak közvetlenül megkaphatóak!
U 3 :={S, A, B} - azok a nemterminálisok, amelyekből U 2 * -beli szavak közvetlenül megkaphatóak.

Mivel U
                  3
                   a nyelvtan összes nemterminálisát tartalmazza, ezért U:=U
                  3
                  =U
                  4
                  =U
                  5
                  =... 
Tehát U-beli nemterminálisokból kapható meg az üresszó.
Mivel SU, ezért az üresszó benne van a G által generált nyelvben.
Készítsük el a G'=({S', S, A, B},{x, y}, S', H') grammatikát, ahol H' a következő szabályokból áll:

  1. S' → S, S' → λ. Ez a két szabály azért került be a H' szabályai közé, mert λ∈L(G), ezért λ∈L(G')-nek is teljesülnie kell!

  2.  Most vegyük azokat a H-beli szabályokat, amelyekben nem a λ szerepel a jobboldalon. Ezek a következők:
    S → AB, A → BSB, A → BB, B → xAy, B → x, B → y.

  3.  És vegyük még azokat a szabályokat, amelyek H-ban nem szerepeltek, és amelyeket úgy kapunk,
    hogy H-beli szabályok jobb oldaláról az összes lehetséges módon
    elhagyjuk U halmaz nemterminálisait, figyelve azonban arra, hogy a jobb oldalon λ ne maradjon
    magában:
    S → A, S → B,
    A → BS, A → SB, A → B, A → S,
    B → xy.


3.33. példa - Üresszó-lemma 2. feladat

Készítsen a következő grammatikával ekvivalens 1-es típusú grammatikát!
G=({S, A, B, C, D}, {a, b}, S,H), ahol H szabályai:
S → AB, A → CB, A → SS, A → a, B → λ,
C → D, D →  λ, D → b.

Megoldás:
U={S,A,B,C,D}
S∈ U, ezért λ∈ L(G), vagyis új kezdőszimbólumot kell bevezetni.
G'=({S',S, A, B, C, D}, {a, b}, S', H'), ahol H' szabályai:

  1. S' → S és S' → λ, mert λ∈ L(G)

  2. S → AB, A → CB, C → D, A → SS, A  → a, D  → b lesznek azok a szabályok H-ból melyekben nem λ van a jobboldalon.

  3. S → A, S → B, A → C, A → B, A  → S lesznek az új szabályok, amelyeket H-beli szabályok jobb oldaláról U-beli nemterminálisok elhagyásával kapunk.

Ez a grammatika ekvivalens a G grammatikával, de már 1-es típusú. ★


3.34. példa - Üresszó-lemma 3. feladat

Küszöbölje ki a törlő szabályokat a G=({S, A, B}, {a, b}, S,H) grammatikából!
 H={S → λ, S → AB, A → SAB, A → a, B → S, B → b}.

Megoldás:
 A feladat az Üresszó-lemma alkalmazásával oldható meg: 
 U={S, B}
 SU, ezért λ∈L(G), vagyis új kezdőszimbólumot kell bevezetni.
 G'=({S',S, A, B}, {a, b}, S', H'), ahol H' szabályai:

  1. S' → S és S' → λ, mert λ∈L(G).

  2. S → AB, A → SAB, A → a, B → S, B  → b lesznek azok a szabályok H-ból, amelyekben nem λ van a jobboldalon.

  3.  
                            S → A, A → SA, A → AB lesznek az új szabályok, amelyeket H-beli szabályok jobb oldaláról
    U-beli nemterminálisok elhagyásával kapunk.
    (Az A → A alakú szabályt nyugodtan elhagyhatjuk, mivel levezetés szempontjából nincs hatása.)


3.35. példa - Üresszó-lemma 4. feladat

             
Küszöbölje ki a törlő szabályokat a G=({S, A, B, C, D, E},{a, d}, S,H) grammatikából!
H={S → SA, S → BS, A → a, B → CDE, C → DddE, C → d, C → λ, D → E, D → d,
 
                  E → λ}.

Megoldás:
A feladat az Üresszó-lemma alkalmazásával oldható meg: 
U={B, C, D, E}
SU, ezért λ∉L(G), vagyis nem kell új kezdőszimbólumot bevezetni.
G'=({S, A, B, C, D, E}, {a, d}, S, H'}), ahol H' szabályai:

  1.  Azok a szabályok H-ból melyekben a jobboldal nem λ:
    S → SA, S → BS, A → a, B → CDE, C → DddE, C → d, D → E, D → d
                         

  2.  Az új szabályok, melyeket U-beli nemterminálisok elhagyásával kapunk:
    B → CD, B → CE, B → DE, B → C, B → D, B → E,
    C → ddE, C → Ddd, C → dd (S → S alakú szabálynak nincs jelentősége.)


3.36. példa - Üresszó-lemma 5. feladat

Hozza a G=({S, A, B, C}, {a, b}, S,H) grammatikát 1-es típusúra!
H={S → ASC, S → BA, B → ACB, B → AA, C → bB, A → λ, A → a, B → ba}.


Megoldás:
U={S, A, B}
SU, ezért λ∈L(G), vagyis új kezdőszimbólumot kell bevezetni.
G'=({S',S, A, B, C}, {a, b}, S', H'), ahol H' szabályai:

  1.  
                            S' → S és S' → λ, mert λ∈L(G).

  2.  
                            S → ASC, S → BA, B → ACB, B → AA, C → bB, A → a, B → ba
    lesznek azok a szabályok H-ból amelyekben nem λ a jobboldal.

  3.  
                            S → AC, S → SC, S → C, S → A, S → B, B → CB, B → AC, B → C, B → A, C → b
    lesznek az új szabályok, amelyeket U-beli nemterminálisok elhagyásával kapunk.