9.4. Normálformák a mondatszerkezetű nyelvtanokhoz

A monoton nyelvtanok definíciójából kitűnik, hogy valójában csak a törlések (rövidítések) lehetősége az amivel a mondatszerkezetű nyelvtanok többet tudhatnak.

Ez valóban így is van, vagyis ha megengedünk akár egyetlen u B vu v, ( BN, u, v∈(NT)* ) alakú szabályt, vagy egy (N, T, S, H) nyelvtanban az SλH használata esetén megengedjük, hogy S szerepeljen szabályok jobb oldalán is, akkor a generáló erő megnő, nem környezetfüggő nyelvek is generálhatóak. Ide kapcsolható a következő eredmény, melyet bizonyítás nélkül közlünk:

79. Tétel. Minden rekurzívan felsorolható nyelv generálható olyan szabályokkal, amelyek mindegyike környezetfüggő ( u B vu r v, BN, u, v, r∈(NT)*, rλ ), kivéve egyetlen A → λ alakú szabályt.

A Penttonen normálformát is kiterjeszthetjük ez alapján mondatszerkezetű nyelvtanokhoz:

24. Definíció. Egy mondatszerkezetű nyelvtant Penttonen normálformájúnak hívunk, ha minden szabálya az alábbi formájúak egyike: A → a, A  → B C, A BA C, Aλ ( A, B, CN, aT). ★

80. Tétel. Minden rekurzívan felsorolható nyelv generálható Penttonen normálformájú mondatszerkezetű nyelvtannal.

Szorosan ide kapcsolódik a következő tétel is, amely azt mutatja, hogy a környezetfüggő és a mondatszerkezetű nyelvek osztálya között nem is olyan nagy a különbség.

81. Tétel. Legyen LT * egy rekurzívan felsorolható nyelv, ekkor van olyan L ' környezetfüggő nyelv, hogy T kiegészíthető egy új betűvel: V=T∪{c} ( cT ), hogy L '⊆c * L és minden wL szóra van olyan n ≥ 0, hogy c n wL '.

Vagyis, ha egy LBA lineárisan korlátozott automatának adjuk oda egy tetszőleges rekurzívan felsorolható nyelv szavait, akkor minden egyes szóra a tárhelyet eléggé megnövelve, LBA el tudja fogadni pontosan a nyelv szavait (illetve azok meghosszabbított, de információt nem tartalmazó változatait). Természetesen a megnövelt tárhely igényű automata már nem feltétlenül lineárisan korlátozott. A következő tétel ezzel összefüggésben hatékonyan használható annak eldöntésére, hogy egyes nyelvek környezetfüggőek.

82. Tétel. (Tárhely tétel) Ha egy adott G mondatszerkezetű nyelvtanra teljesül, hogy létezik olyan k konstans, hogy benne bármely tetszőleges wL(G) nemüres szót levezetve van olyan levezetés amiben a mondatforma hossza soha nem hosszabb a k⋅|w| értéknél, akkor L(G) környezetfüggő.

Ebben a fejezetben több fontos további normálformát mutatunk be (bizonyítás nélkül), amelyek a mondatszerkezetű és egyéb nyelvosztályok kapcsolatára is rávilágítanak.

9.4.1. Révész-féle normálalak

A következő normálalak a Kuroda-féle normálalak Révész-féle észrevétellel kiegészített alakjának általánosítása a mondatszerkezetű nyelvtanokra.

83. Tétel. Minden rekurzívan felsorolható nyelv generálható olyan nyelvtannal, amelyben a szabályok alakja a következő hétféle alakúak lehetnek:

S → λ,

A → a,

A → B,

A → B C,

A BA C,

A BC B,

A B → B,

ahol aT, A, B, CN,

és az S mondatszimbólum nem fordul elő egyik szabály jobboldalán sem.

9.4.2. Geffert-féle normálformák

V. Geffert bizonyította, hogy a törlő (rövidítő) szabályok és a környezetfüggő (monoton) nyelvtanoknak az tulajdonsága, hogy egy szabály bal oldalán egynél több betű is állhat, akár egy közös szabályalakkal is figyelembe vehető. Az itt bemutatandó normálformák közös tulajdonsága, hogy bennük a környezetfüggetlen szabályok mellett csak olyan szabályok jelennek meg, melyek jobboldala az üresszó.

84. Tétel. Minden rekurzívan felsorolható nyelv generálható olyan (N, T, S, H) nyelvtannal, amelyben 5 nemterminális van (N={S,A,B,C,D}), minden szabály S → v alakú (vagyis környezetfüggetlen és a startszimbólum van a bal oldalon); és még két szabály: A Bλ, C Dλ.

85. Tétel. Minden rekurzívan felsorolható nyelv generálható olyan (N, T, S, H) nyelvtannal, amelyben 4 nemterminális van (N={S,A,B,C}), minden szabály S → v alakú (vagyis környezetfüggetlen alakú és a startszimbólum van a bal oldalon); és még két szabály: A Bλ, C Cλ.

86. Tétel. Minden rekurzívan felsorolható nyelv generálható olyan (N, T, S, H) nyelvtannal, amelyben 3 nemterminális van (N={S,A,B}), minden szabály S → v alakú (vagyis környezetfüggetlen és a startszimbólum van a bal oldalon); és még két szabály: A Aλ, B B Bλ.

87. Tétel. Minden rekurzívan felsorolható nyelv generálható olyan (N, T, S, H) nyelvtannal, amelyben 3 nemterminális van (N={S,A,B}), minden szabály S → v alakú (vagyis környezetfüggetlen és a startszimbólum van a bal oldalon) egy kivételével: A B B B A  → λ.

88. Tétel. Minden rekurzívan felsorolható nyelv generálható olyan (N, T, S, H) nyelvtannal, amelyben 4 nemterminális van (N={S,A,B,C}), minden szabály S → v alakú (vagyis környezetfüggetlen és a startszimbólum van a bal oldalon) egy kivételével: A B Cλ.