6.4. A lineáris nyelvek tulajdonságai

6.4.1. Iterációs lemma

Lineáris nyelvekre a következő pumpálási (iterációs) tulajdonságot fogjuk bizonyítani:

39. Tétel. Legyen L egy lineáris nyelv. Ekkor létezik olyan (a nyelvtől függő) n természetes szám, hogy minden zL szóra, melyre |z|>n, van a szónak olyan z=u v w x y felbontása amelyre teljesülnek a következő feltételek

1. u v i w x i yL minden i természetes számra ( i ≥ 0 )

2. |v x|>0

3. |u v x y| ≤ n.

Bizonyítás. Tegyük fel, hogy L nyelv lineáris, ekkor legyen G=(N, T, S, H) olyan lineáris nyelvtan, amely L-et generálja és erős normálformában van. Legyen n=|N|+2. Ekkor legyen wL tetszőleges olyan szó, amelyre |w|>n. Tekintsük w levezetési fáját. Mivel miden lépésben pontosan egy terminális kerül bevezetésre a levezetés hossza (lépéseinek száma) éppen megegyezik a szó hosszával. A levezetési fa főága (amely tartalmazza a levezetés során szereplő összes nemterminálist és egy terminális levélelemet) legalább |N|+1 nemterminális szimbólumot tartalmaz, tehát legalább egy nemterminálist kétszer tartalmaz az első |N|+1 eleme közt. Legyen ez a nemterminális A. A első előfordulásakor a levezetés u A y mondatformánál tart (definiáljuk ezzel az u és y részszavakat), míg az A második előfordulásakor legyen az u v A x y az aktuális mondatforma (definiáljuk így a v és x részszavakat), Végül legyen A* w az A második előfordulásából generált részszó. Ennek megfelelően világos, hogy A* v w x az A első előfordulásából generált részszó, valamint A* v A x mondatforma. Amennyiben az A első előfordulásakor a levezetés folytatása u A y* u w y, akkor éppen az i=0 esetbeli szót vezethetjük le. Ha az A második előfordulásakor nem a w hanem v w x szót vezetjük le belőle, akkor kapjuk az i=2 esetnek megfelelő szót, viszont ebben a levezetésben u A y* u v A x y* u v v A x x y mondatforma is szerepel, ahol az A-ból a w helyett az u w y szót levezetve az i=3 esetbeli iterált szót kapjuk és így tovább. Az i értéke bármely természetes számra növelhető. Az eredeti felosztásunk és az erős normálforma miatt a |v x|>0 és az |u v x y| ≤ n feltételek automatikusan teljesülnek. Ezzel a bizonyítást befejeztük. ∎

Sajnos az iterációs lemma nem adja szükséges és elégséges feltételét annak, hogy egy nyelv lineáris legyen, vagyis ha a nyelv lineáris akkor a lemma feltételeinek szükségszerűen teljesülnie kell, viszont ha teljesül a lemma valamely nyelvre az még nem elégséges bizonyíték arra, hogy a nyelv lineáris legyen. Ezek alapján a lemmát arra használhatjuk, hogy amennyiben sikerül belátnunk egy adott nyelvről, hogy nem teljesülnek rá a lemma feltételei, akkor a nyelv biztosan nem lineáris.

6.13. példa - Lineáris iterációs lemma alkalmazása

Legyen L={ a k b k a m b m | k, m>0}. Az iterációs lemma segítségével belátjuk, hogy L nyelv nem lineáris. Tegyük fel, indirekt, hogy L lineáris. Ekkor L-re teljesülnie kell a lemmának. Legyen n az a konstans ami a lemma alapján ehhez a nyelvhez tartozik. Vegyük az a 2n b 2n a 2n b 2n alakú szót, ami eleme L-nek, másrészt a hossza 8n, így nagyobb, mint n. Tehát a szót fel kell tudnunk bontani u v w x y részszavakra, hogy v és x nem lehet egyszerre az üresszó, valamint |u v x y| ≤ n. Viszont ekkor |u v| ≤ n és |x y| ≤ n is fennáll, vagyis v csak az első a 2n beli résznek lehet részszava, így ha nem nulla a hossza, akkor a i (0<i ≤ n) alakú. Viszont az első b 2n blokk egésze csak a w-hez tartozhat. Így az iteráció során az első a-kból álló blokkban az a-k száma megváltozna, míg a hozzátratozó első b-ket tartalmaz blokk maradna b 2n . Így nem L-beli szót kapunk, tehát v-nek az üresszónak kell lennie. Ekkor viszont x nem lehet üres és csak az utolsó b 2n blokkból tartalmazhat betűket. Az előző esettel analóg módon belátható, hogy a pumpálás kivezet az L nyelvből, ha x nem az üresszó. De v és x nem lehet egyszerre üres a lemma állítása miatt. Az ellentmondást csak az indirekt feltételünk okozhatja, tehát a nyelv nem lineáris. ★


6.4.2. Zártsági tulajdonságok

40. Tétel. A lineáris nyelvek osztálya zárt az unió műveletre.

Bizonyítás. Legyenek L 1 és L 2 lineáris nyelvek G 1=(N 1, T, S 1, H 1) és G 2=(N 2, T, S 2, H 2) lineáris nyelvtanokkal, ahol N 1 és N 2 diszjunkt halmazok. Konstruáljuk meg az (N 1N 2∪{S}, T, S, H) nyelvtant, ahol S új szimbólum, nem szerepel sem N 1, sem N 2 elemei közt, H pedig a következőképpen definiált: H=H 1H 2∪{S  → S 1, S  → S 2}. Könnyen belátható, hogy az új nyelvtan lineáris és éppen L 1 és L 2 unióját generálja. ∎

41. Tétel. A lineáris nyelvek osztálya nem zárt a konkatenációra, a Kleene-iterációra.

Bizonyítás. Korábbi példaként láttuk, hogy L={a n b n | n>0} lineáris nyelv, saját magával konkatenálva az L L={a k b k a m b m | k, m>0} nyelvet kapjuk, amiről az imént mutattuk meg, hogy nem lineáris. Mivel L LL *, ennek esetünkben egyenes következménye, hogy L * nyelv sem lineáris. ∎

42. Tétel. A lineáris nyelvek osztálya nem zárt a metszet és a komplementer műveletekre.

Lásd környzetfüggetlen nyelvekre vonatkozó 56. és 57. tételben.

A továbbiakban a lineáris nyelvtanoknak (és nyelveknek) speciális alosztályát, illetve kiterjesztését vizsgáljuk. Amar és Putzolu az 1960-as években definiálta a következő, a reguláris és a lineáris nyelvcsaládok közti nyelvosztályokat.

12. Definíció. Legyen k egy rögzített nemnegatív racionális szám. Ha egy G lineáris nyelvtan minden Au B v alakú szabályára igaz, hogy , akkor G-t k-arányú (vagy k-fokú) lineáris nyelvtannak, az általa generált nyelvet pedig k-arányú lineáris nyelvnek hívjuk. Egy nyelvtant (illetve nyelvet) fix-arányú lineárisnak nevezünk, ha k-arányú lineáris valamely nemnegatív racionális k értékre. ★

Speciális esetben k=0 érték esetén éppen a reguláris nyelveket kapjuk vissza. Nevezetes még a k=1 eset, ezeket a nyelveket és nyelvtanokat páros lineárisnak hívjuk. Erre példa a palindromák nyelve.

43. Tétel. Minden k nemnegatív racionális számra, a k-fokú lineáris nyelvek osztálya tartalmazza a reguláris nyelvek osztályát.

44. Tétel. Minden fix-arányú lineáris L nyelvhez létezik olyan determinisztkus 2-fejű automata, ami éppen L-et fogadja el.

13. Definíció. Egy G=(N, T, S, H) nyelvtant m-lineárisnak nevezünk (ahol m>0 egész szám), ha szabályainak mindegyike eleget tesz a lineáris nyelvtanoknál megadott definíciónak, kivéve az egyetlen SS 1 S 2S m szabályt, és S nem szerepel egyik szabály jobb oldalán sem. Az m-lineáris nyelvtanok által generált nyelvek osztályát m-lineáris nyelvek osztályának nevezzük. Egy nyelvtan, illetve nyelv metalineáris ha m-lineáris valamilyen m-re. ★

Egy metalineáris nyelvtanban a mondatformában már több nemterminális is előfordulhat egyszerre, de számuk maximálva van, ha a nyelvtan m-lineáris, akkor maximum m nemterminális lehet egyszerre. A lineáris nyelvek konkatenációjával éppen a metalineáris nyelveket állíthatjuk elő.

6.14. példa - Az akbkambm metalineáris nyelv

G=({S, A, B}, {a, b}, S, {S → A B, A → a A b, Aa b, B → a B b, Ba b}) nyelvtan éppen a korábban már bemutatott {a k b k a m b m | k, m>0} nyelvet generálja. ★


A következő ábrán a lineáris nyelvekhez kapcsolódó hierarchiát mutatjuk be, a hierarchia éles, vagyis minden tartalmazás szigorú (kivéve a k=0 és m=1 eseteket, amikor a 0-fokú lineáris nyelvek éppen a reguláris az 1-lineáris nyelvek, pedig éppen a lineáris nyelvekkel esnek egybe).