8.2. Normálformák a környezetfüggő nyelvtanokhoz, a monoton és a környezetfüggő nyelvtanok ekvivalenciája

A normálformák itt is nagy jelentőséggel bírnak. Az első normálforma amivel megismerkedünk, a szabályok hosszát korlátozza: csak olyan terminális normális alakú monoton szabályokat engedünk meg, amelyekben a jobboldal hossza maximum kettő.

17. Definíció. Egy monoton nyelvtanról azt mondjuk, hogy Kuroda-féle normálalakban van, ha minden szabálya az alábbi alakok egyikében van: A → B, A  → B C, Aa, A BC D(aT, A, B, C, DN). ★

59. Tétel. Minden monoton nyelvtanhoz van vele ekvivalens Kuroda normálformájú nyelvtan.

Bizonyítás. A bizonyítás konstruktív, minden G monoton nyelvtan esetén hatékonyan megkonstruálhatjuk azt a Kuroda normálformájú nyelvtant, amely az L(G)∖{λ} nyelvet generálja: Legyen tehát adott G=(N, T, S, H) monoton nyelvtan.

Az algoritmus első lépésével (ugyanúgy, mint pl. a Chomsky normálforma esetén) elérjük, hogy a terminális szimbólumok csak A → a alakú szabályokban forduljanak elő: ehhez vezessünk be minden terminális szimbólumhoz egy-egy a nyelvtanban még nem szereplő új nemterminális szimbólumot: tehát legyen N '={X a |aT}, miközben NN '=∅. Állítsuk elő a H ' szabályrendszert a H- ból a következőképpen: a H minden szabályában szereplő minden a terminálist helyettesítsünk a neki megfelelő X a újonnan bevezetett nemterminálissal és így másoljuk át a H '- be és adjuk még hozzá az X a a alakú szabályokat minden aT -re. Ekkor G '=(NN ', T, S, H ') ekvivalens G- vel és benne terminálisok csak Xa  → a alakú szabályokban fordulnak elő.

Második lépésben, ha p → qH, ahol p=A 1A m és q=B 1B n , akkor világos a nyelvtan definíciójából következően, hogy m ≤ n. Ekkor vegyük sorra a szabályokat és járjunk el a következő módon:

- ha n ≤ 2, akkor a szabály eleget tesz a Kuroda normálformának.

- ha m=1, n>2, akkor (ugyanúgy, mint a Chomsky normálformára alakításnál; lásd Chomsky-féle normálalak) helyettesítsük az AB 1B n szabályt AB 1 C 1, C 1B 2 C 2, …, C n-2B n-1 B n szabályokkal, ahol a C 1, …, C n-2 újonnan bevezetett, csak itt szereplő nemterminálisok.

- ha m ≥ 2, n>2, akkor a C 1, C 2, …, C n-2 újonnan bevezetett, és csak itt szereplő, nemterminálisok segítségével hozzuk létre a következő szabályokat az eredeti szabály helyettesítésére: A 1 A 2B 1 C 1, C 1 A 3B 2 C 2, …, C m-2 A m B m-1 C m-1, C m-1B m C m , …, C n-2B n-1 B n .

Az új nyelvtan Kuroda normálformájú és ekvivalens az eredetivel. ∎

8.2. példa - Kuroda normálforma 1.feladat


Adjunk meg a G=({S,A,B},{x,y,z},S,H) környezetfüggő nyelvtannal ekvivalens Kuroda-féle
normálalakú nyelvtant, ahol
H={ S →  ABABx, ABA →  AyyyA, Ayyy →  Byyy, A →  z, A →  BB, B →  S, B →  x }.



Megoldás:
(I.) Első lépésben megadunk egy G
            1 nyelvtant, ami ekvivalens a G nyelvtannal és terminális csak
X → a alakú szabályban fordul elő (XNa∈ T).
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 normálalakú szabályban szerepelnek, Xi
            
-re cseréljük.
 
Jelen esetben legyenek az új nemterminálisok az X és az Y, ekkor:
G
            1
            =({S,A,B,X,Y},{x,y,z},S,H
            1), ahol
H
            1
            ={ X →  x, Y →  y, S →  ABABx, ABA →  AyyyA, Ayyy →  Byyy, A →  z, A →  BB, B →  S, B →  x }


(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 ≥ 3 alakú szabály.
Ehhez a G
            1 nyelvtanból indulunk ki.
H
            1
             szabályhalmaz Y →  Y
            1
            Y
            2
            ...Yn
            
n ≥ 3 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 ≥ 3 alakú szabályhoz
vezessünk be Z
            1
            ,Z
            2
            , ... ,Z
            
               n-2
 nemterminálisokat, ahol a Zi
            
-ből pontosan az Y
            
               i+1
Y
            
               n
            
 szót fogjuk levezetni:
az összes  Y →  Y
            1
            Y
            2
            ...Yn
            
n ≥ 3 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,X,Y,Z
            1
            ,Z
            2
            ,Z
            3},{x,y,z},S,H
            2), ahol
H
            2
            ={ X →  x, Y →  y, S →  AZ
            1
            , Z
            1
             →  BZ
            2
            , Z
            2
             →  AZ
            3
            , Z
            3
             →  BX, ABA →  AYYYA, AYYY →  BYYY,
 A →  z, A →  BB, B →  S, B →  x }
 


(III.) Harmadik lépésben megadjuk az eredeti nyelvtannal ekvivalens G' Kuruda-féle normá alakú
nyelvtant.
Ehhez a G
            2 nyelvtanból indulunk ki.
H
            2 szabályhalmaz X
            1
            X
            2
             ... Xn →  Y
            1
            Y
            2
             ... Ym
            
n ≥ 2, m ≥ 3 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' szabályhalmazba.
Minden X
            1
            X
            2
             ... Xn →  Y
            1
            Y
            2
             ... Ym
            
n ≥ 2, m ≥ 3 alakú szabályhoz vezessünk be
Z
            1
            ,Z
            2
            , ...,Z
            
               m-2
 új nemterminálisokat!
Ezek után az
X
            1
            X
            2
             ... Xn →  Y
            1
            Y
            2
             ... Ym
            
n ≥ 2, m ≥ 3 alakú szabályokat helyettesítsük a következő szabályokkal:
X
            1
            X
            2
             →  Y
            1
            Z
            1
            ,

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

            Xn →  Y
            
               n-1

            Z
            
               n-1

            ,

            Z
            
               n-1

             →  YnZn,
.
.
.
Z
            
               m-3

             →  Y
            
               m-2

            Z
            
               m-2

            ,

            Z
            
               m-2

             →  Y
            
               m-1

            Ym.

Jelen esetben:
G'=({S,A,B,X,Y,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4
            ,Z
            5
            ,Z
            6
            ,Z
            7
            ,Z
            8},{x,y,z},S,H'), ahol
H'={ X →  x, Y →  y, S →  AZ
            1
            , Z
            1
             →  BZ
            2
            , Z
            2
             →  AZ
            3
            , Z
            3
             →  BX, AB →  AZ
            4
            , Z
            4
            A →  YZ
            5
            , Z
            5
             →  YZ
            6
            ,

            Z
            6
             →  YA, AY →  BZ
            7
            , Z
            7
            Y →  YZ
            8
            , Z
            8
            Y →  YY, A →  z, A →  BB, B →  S, B →  x } ★
 

8.3. példa - Kuroda normálforma 2.feladat


Adjunk meg a G=({S,A,B},{a,b,c},S,H) környezetfüggő nyelvtannal ekvivalens Kuroda-féle
normálalakú nyelvtant, ahol
H={ S →  BaB, BaB →  BaBa, A →  SaS, A →  c, B →  AbbA, B →  c }.
 



Megoldás:
(I.) Legyenek az új nemterminálisok az X és az Y, ekkor:
G
            1
            =({S,A,B,X,Y},{a,b,c},S,H
            1), ahol
H
            1
            ={ X →  a, Y →  b, S →  BXB, BXB →  BXBX, A →  SXS, A →  c, B →  AYYA, B →  c }
(II.)
G
            2
            =({S,A,B,X,Y,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4},{a,b,c},S,H
            2), ahol
H
            2
            ={ X →  a, Y →  b, S →  BZ
            1
            , Z
            1
             →  XB, BXB →  BXBX, A →  SZ
            2
            , Z
            2
             →  XS, A →  c,

            B →  AZ
            3
            , Z
            3
             →  YZ
            4
            , Z
            4
             →  YA, B →  c }
(III.)
G'=({S,A,B,X,Y,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4
            ,Z
            5
            ,Z
            6},{a,b,c},S,H'), ahol
H'={ X →  a, Y →  b, S →  BZ
            1
            , Z
            1
             →  XB, BX →  BZ
            5
            , Z
            5
            B →  XZ
            6
            , Z
            6
             →  BX,

            A →  SZ
            2
            , Z
            2
             →  XS, A →  c, B →  AZ
            3
            , Z
            3
             →  YZ
            4
            , Z
            4
             →  YA, B →  c} ★
 

8.4. példa - Kuroda normálforma 3.feladat


Adjunk meg a G=({S,A,B},{a,b},S,H) környezetfüggő nyelvtannal ekvivalens
Kuroda-féle normálalakú nyelvtant, ahol
H={ S →  AB, AB →  ABAA, ABA →  ABAABB, B →  S, A →  a, B →  b, A →  SA }.


Megoldás:
(I.)
Mivel a G nyelvtan már normálalakban van, ezért  G
            1
            =G.
(II.)
Mivel a G
            1 nyelvtanban nincs Y →  Y
            1
            Y
            2
            ...Yn
            
n ≥ 3 alakú szabály,
ezért G
            2
            =G
            1.
(III.)
G'=({S,A,B,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4
            ,Z
            5
            ,Z
            6},{a,b},S,H'), ahol
H'={ S →  AB, AB →  AZ
            1
            , Z
            1
             →  BZ
            2
            , Z
            2
             →  AA, AB →  AZ
            3
            , Z
            3
            A →  BZ
            4
            , Z
            4
             →  AZ
            5
            ,

            Z
            5
             →  AZ
            6
            , Z
            6
             →  BB, B →  S, A →  a, B →  b, A →  SA} ★

8.5. példa - Kuroda normálforma 4.feladat

            
Adjunk meg a G=({S,A,B},{0,1},S,H) hosszúság nemcsökkentő nyelvtannal ekvivalens Kuroda-féle
normálalakú nyelvtant, ahol
H={ S →  SAS, SA →  B0B0S, S →  1, A →  S0S, B0B0 →  0S0S }.
 



Megoldás:
(I.) Legyen az új nemterminális a C, ekkor:
G
            1
            =({S,A,B,C},{0,1},S,H
            1), ahol
H
            1
            ={ C →  0, S →  SAS, SA →  BCBCS, S →  1, A →  SCS, BCBC →  CSCS }
(II.)
G
            2
            =({S,A,B,C,Z
            1
            ,Z
            2},{0,1},S,H
            2), ahol
H
            2
            ={ C →  0, S →  SZ
            1
            , Z
            1
             →  AS, SA →  BCBCS, S →  1, A →  SZ
            2
            , Z
            2
             →  CS, BCBC →  CSCS }
(III.)
 G'=({S,A,B,C,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4
            ,Z
            5
            ,Z
            6
            ,Z
            7},{0,1},S,H'), ahol
H'={ C →  0, S →  SZ
            1
            , Z
            1
             →  AS, SA →  BZ
            3
            , Z
            3
             →  CZ
            4
            , Z
            4
             →  BZ
            5
            , Z
            5
             →  CS,

            S →  1, A →  SZ
            2
            , Z
            2
             →  CS, BC →  CZ
            6
            , Z
            6
            B →  SZ
            7
            , Z
            7
            C →  CS } ★
 

8.6. példa - Kuroda normálforma 5.feladat


Adjunk meg a G=({S,B},{a,b,c},S,H) hosszúság nemcsökkentő nyelvtannal ekvivalens Kuroda-féle
normálalakú nyelvtant, ahol
H={ S →  abc, S →  aSBc, cB →  Bc, bB →  bb }.
 



Megoldás:
(I.) Legyenek az új nemterminálisok az AE és a C, ekkor:
G
            1
            =({S,B,A,E,C},{a,b,c},S,H
            1), ahol
H
            1
            ={ A →  a, E →  b, C →  c, S →  AEC, S →  ASBC, CB →  BC, EB →  EE }
(II.)
G
            2
            =({S,B,A,E,C,Z
            1
            ,Z
            2
            ,Z
            3},{a,b,c},S,H
            2), ahol
H
            2
            ={ A →  a, E →  b, C →  c, S →  AZ
            1
            , Z
            1
             →  EC, S →  AZ
            2
            , Z
            2
             →  SZ
            3
            ,

            Z
            3
             →  BC, CB →  BC, EB →  EE }
(III.)
Mivel a G
            2 nyelvtan már Kuroda-féle normálalakban van, ezért G'=G
            2. ★
 

8.7. példa - Kuroda normálforma 6.feladat

            
Adjunk meg a G=({S,A,B},{d,e},S,H) hosszúság nemcsökkentő nyelvtannal ekvivalens Kuroda-féle
normálalakú nyelvtant, ahol
H={ S →  BeBe, BeBe →  dAdA, eB →  dede, Bd →  SAS, A →  ede }.
 



Megoldás:
(I.) Legyenek az új nemterminálisok a D és az E, ekkor:
G
            1
            =({S,A,B,D,E},{d,e},S,H
            1), ahol
H
            1
            ={ D →  d, E →  e, S →  BEBE, BEBE →  DADA, EB →  DEDE, BD →  SAS, A →  EDE }
(II.)
G
            2
            =({S,A,B,D,E,Z
            1
            ,Z
            2
            ,Z
            3},{d,e},S,H
            2), ahol
H
            2
            ={ D →  d, E →  e, S →  BZ
            1
            , Z
            1
             →  EZ
            2
            , Z
            2
             →  BE, BEBE →  DADA, B →  DEDE,

            BD →  SAS, A →  EZ
            3
            , Z
            3
             →  DE }
(III.)
G
            2
            =({S,A,B,D,E,Z
            1
            ,Z
            2
            ,Z
            3
            ,Z
            4
            ,Z
            5
            ,Z
            6
            ,Z
            7
            ,Z
            8},{d,e},S,H'), ahol
H'={ D →  d, E →  e, S →  BZ
            1
            , Z
            1
             →  EZ
            2
            , Z
            2
             →  BE, BE →  DZ
            4
            , Z
            4
            B →  AZ
            5
            , Z
            5
            E →  DA,

            EB →  DZ
            6
            , Z
            6
             →  EZ
            7
            , Z
            7
             →  DE, BD →  SZ
            8
            , Z
            8
             →  AS, A →  EZ
            3
            , Z
            3
             →  DE } ★
 

A Kuroda-féle normálformát a Révész György nevéhez fűződő észrevétellel tovább alakíthatjuk.

Révész-trükk

Egy A BC D alakú monoton szabály helyettesíthető a következő négy szabállyal, ahol A ' és B ' újonnan bevezetett nemterminálisok:


               A
               B → A 'B

               A 'B → A 'B '
A 'B ' → C
               B '
C
               B ' → C
               D

            

Figyeljük meg, hogy az újonnan bevezetett szabályok mindegyike eleget tesz a környezetfüggő nyelvtanoknál előírt megszorításoknak. Ez alapján kimondhatjuk a következő tételt.

60. Tétel. Minden monoton nyelvtanhoz van vele ekvivalens, aminek szabályai csak A → B, A  → B C, Aa, A BA C, A BC B alakúak lehetnek ( aT, A, B, CN ).

Ezzel egyúttal azt is bizonyítottuk, hogy minden monoton nyelvtannal generálható nyelv generálható környezetfüggő nyelvtannal is. Mivel a másik irányú tartalmazás a nyelvtantípusok definíciójából adódóan nyilvánvaló (vagyis minden környezetfüggő nyelvtan egyben monoton is), ezért :

5. Következmény. A monoton és a környezetfüggő nyelvtanok által generált nyelvek osztálya megegyezik (így, most már jogosan hívhatjuk a monoton nyelvtanok által generált nyelveket környezetfüggőnek).

További normálformákat mutatunk a környezetfüggő nyelvosztályhoz (bizonyítások nélkül).

Cremers normálforma (lánc szabályok kiküszöbölése):

61. Tétel. Minden környezetfüggő nyelvtanhoz van vele ekvivalens, melynek szabályai csak a következő alakúak lehetnek:

A → a, A  → B C, A BC D.

Révész-féle egyoldali normálforma:

18. Definíció. Egy nyelvtan Révész-féle egyoldali normálformájú, ha szabályai csak A → a, A  → B, AB C, A BA C, A BB A alakúak lehetnek ( aT, A, B, CN). ★

62. Tétel. Minden környezetfüggő nyelvtanhoz van vele ekvivalens Révész-féle egyoldali normálformájú nyelvtan.

10. Megjegyzés. Révész-féle egyoldali normálformájú nyelvtanban csak egyoldali környezetfüggés megengedett, viszont permutációs szabály (helycsere) használható (ami nem tesz eleget a környezetfüggő definíciónak).

Felmerülhet a kérdés, hogy vajon mindkét típusú nem környezetfüggetlen szabályra szükség van-e ahhoz, hogy (minden) környezetfüggő nyelvet generálni tudjunk.

A permutációs nyelvek esetében környezetfüggetlen szabályok mellé A BB A alakú szabályokat véve nem környezetfüggetlen, környezetfüggő nyelveket is generálhatunk. (lásd, a következő alfejezetben: Permutációs nyelvek). Az előző kérdésre a választ a következő egyoldali normálforma adja meg:

19. Definíció. Egy környezetfüggő nyelvtanról azt mondjuk, hogy Penttonen normálformában van, ha minden szabályára illik az alábbi alakok egyike A → a, A  → B C, A BA C(aT, A, B, CN). ★

63. Tétel. Minden környezetfüggő nyelvtannal van ekvivalens olyan, amely Penttonen normálalakú.

A normálformák bevezetése során egyrészt a szabályok hosszának korlátozása volt fontos, másrészt a különböző típusú rekurziók kiküszöbölése, pl. egy (egyszerű és nem teljesen jól megírt) számítógépprogram könnyen végetlen ciklusba kerülhet, egy jól megírt program pedig sokkal összetettebb kell, hogy legyen, ha valamilyen rekurziót engednek meg a nyelvtan szabályai, hiszen az előforduló rekurziók némelyikét külön kezelni kell.

A környezetfüggetlen esetben a Chomsky-féle normálalak egyik nagy előnye, hogy a láncszabályok által okozott rekurzió (pl. A → B, B  → C, CA ) nem okozhat gondot, - minden lépésben vagy nő a mondatforma hossza, vagy terminálist vezetünk be, - ezért működik jól pl. a CYK algoritmus. A láncszabályok a környezetfüggő esetben is kiküszülhetőek, ahogy a Cremers és a Penttonen-féle normálformák sem tartalmaznak ilyet.

A Greibach normálforma Greibach normálforma a balrekurziót küszöböli ki, ezért ugyancsak fontos lehet néhány szóelemző algoritmus számára (legbalodali levezetés esetén).

Környezetfüggő esetben viszont, az eddig általunk legerősebbnek vélt normálforma is megenged rekurziót: a nem környezetfüggetlen szabályok esetén a mondatforma hossza nem változik.

Környezetfüggő rekurziónak nevezzük azt, ha csupán A BA C alakú szabályok segítségével egy levezetés "körbe mehet", vagyis vannak olyan E és F nemterminálisok, hogy E F+ E F, vagyis valahány (nem nulla) lépés után ismétlődés léphet fel. Egy ilyen egyszerű ismétlődést generálhat pl. az A BA C és A CA B szabályok együttes jelenléte.

Egy nyelvtant rekurzió-mentes normálformájúnak hívunk, ha Penttonen normálformájú és környezetfüggő rekurzió nincs benne. A következő tétel Nagy Benedek és Varga Péter nevéhez fűződik:

64. Tétel. Minden környezetfüggő nyelvtanhoz van vele ekvivalens, ami rekurzió-mentes normálformájú.