5. fejezet - Reguláris nyelvek

A reguláris nyelvek alkotják a Chomsky-féle hierarchia legkisebb osztályát. Ezzel a nyelvosztállyal kapcsolatosan számos elméleti eredmény ismert, és ezek a nyelvek a gyakorlatban is számos helyen alkalmazhatóak.

Emlékeztetőül, egy nyelvtanról akkor mondjuk, hogy reguláris, ha minden egyes szabálya A → u B vagy A → u alakú (ahol A, BN, uT *).

Elsőként azt a bárkiben felmerülő kérdést tisztázzuk, hogy mi a véges és a reguláris nyelvek viszonya.

19. Tétel. Minden véges nyelv reguláris.

Bizonyítás. Legyen L={w 1, …, w n } véges nyelv (megadhatjuk az elemeinek felsorolásával) valamilyen T ábécé felett, ekkor a G=({S}, T, S, {Sw i | w i L}) nyelvtan pont L- et generálja. Másrészt G minden szabályára igaz, hogy a jobboldalon csak terminálisok szerepel(het)nek, így G reguláris. ∎

A következő egyszerű példa azt mutatja, hogy vannak végtelen reguláris nyelvek is:

5.1. példa - Végtelen reguláris nyelv

Legyen G=({S}, {a}, S, {Sa a S, S → a a}). Ekkor a generált nyelv L={a 2n | n ≥ 1}. ★


2. Következmény. A véges nyelvek halmaza valódi része a reguláris nyelvek halmazának.

A reguláris nyelvtanok esetén levezetéseket nagyon egyszerű, csúcscímkézett fagráfokkal tudjuk reprezentálni: A kiinduló gyökércsúcs címkéje az S mondatszimbólum. Egy A nemterminális címkéjű csúcsból, ha arra már alkalmaztunk egy Aa 1a k B megfelelő levezetési szabályt ( k ≥ 0 a szabályban szereplő terminálisok száma, k=0 esetben A → B a szabály alakja), k+1 él indul, és a gyerekcsúcsok címkéje balról jobbra haladva a 1, …, a k , valamint B. Ha a levélelemek közt van nemterminális címkéjű, akkor a fa egy még be nem fejezett levezetést ábrázol, ilyenkor pontosan egy nemterminális címkéjű levélcsúcs van. Ha nincs nemterminális címkéjű levél, akkor az ábrázolt levezetés befejezett (termináló). A terminális címkéjű csúcsok levélelemei minden levezetési fának.

A mondatformát, illetve a levezetett szót megkapjuk, ha a levelek címkéit balról jobbra haladva elolvassuk.

5.1. Normálformák a reguláris nyelvtanokhoz

A Chomsky-féle nyelvosztályok definíciójában megengedtük, hogy egy lépésben bármennyi terminális bekerülhet a mondatformába, vagyis a szabályok jobb oldalának hosszára nem adtunk korlátot. Most megmutatjuk, hogy minden reguláris nyelv generálható speciálisabb formájú nyelvtanokkal is.

8. Definíció. Egy reguláris nyelvtanról azt mondjuk, hogy gyenge normálformában van, ha minden szabályára teljesül az alábbi alakok egyike: A → a B, A → B, A  → a, Aλ (ahol A, BN, aT). ★

20. Tétel. Minden reguláris nyelv generálható gyenge normálformájú reguláris nyelvtannal.

Bizonyítás.. Legyen adva G=(N, T, S, H) reguláris nyelvtan. Ez alapján fogjuk elészíteni a G '=(N ', T, S, H ') nyelvtant, hogy a generált nyelv ne változzon meg, de H ' csak olyan alakú szabályokat tartalmazzon, amikben maximum egy terminális szerepel. Az eredeti definícióban megengedett, hogy egynél több terminális szerepeljen egy szabály jobboldalán, ezeket kell helyettesítenünk a normálformának eleget tevő szabályok sorozataival. Vegyük sorra tehát a H szabályait:

Ha az aktuális szabályra teljesül az A → a B, A → B, A  → a, Aλ alakok egyike, akkor őt változtatás nélkül másoljuk át H- ból, H '- be. Ha az aktuális szabályra nem teljesül a fenti alakok egyike sem, akkor a következő két eset lehetséges:

- a szabály alakja Aa 1a k ( k>1, a 1, …, a k T) . Ekkor vegyük fel az N ' halmazba, az eddig még nem szereplő X 1, …, X k-1 nemterminálisokat, és az aktuális szabály helyett a H '- be vegyük fel a Aa 1 X 1, X 1a 2 X 2, …, X k-2a k-1 X k-1, X k-1a k szabályokat.

- a szabály alakja Aa 1a k B ( k>1, a 1, …, a k T) . Ekkor vegyük fel az N ' halmazba, az eddig még nem szereplő X 1, …, X k-1 nemterminálisokat, és az aktuális szabály helyett a H '- be vegyük fel a Aa 1 X 1, X 1a 2 X 2, …, X k-1a k B szabályokat.

Majd tekintsük ugyanilyen eljárás során a kövtekező szabályt H- ból.

Az eljárásunk végén G ' gyenge normálformájú reguláris nyelvtan lesz, továbbá benne minden újonnan bevezetett nemterminális pontosan két szabályban szerepel, egyszer a jobb oldalon, egyszer a baloldalon. Ha egy olyan szabályt alkalmazunk, aminek a jobb oldalán új ( N- ben nem szereplő) nemterminális van, akkor a levezetés csak úgy folytatódhat, ha azt a szabályt alkalmazzuk, ahol ez a nemterminális van a bal oldalon. Ily módon végig kell alkalmaznunk az eredetileg alkalmazott szabályt helyettesítő lánc szabályait. Ennek alapján indukcióval belátható, hogy a G és a G ' által generált nyelv megegyezik. ∎

A fenti ábrán látható, hogy a normálformára hozás tekinthető a levezetési fák olyan transzformációjának, aminek ereményeként bináris (minden csúcsban maximum ketté ágazó) fa áll elő; miközben a levélelemek száma és sorrendje nem változik.

Az előző normálforma tovább alakítható. Az A → λ alakú szabályok kiküszöbölhetőek az Üresszó-lemmánál bizonyított módon (Üresszó-lemma). Így elérhető, hogy vagy ( λ- mentes nyelv esetén) egyáltalán nem fordul elő olyan szabály, aminek jobboldala az üresszó, vagy (ha a nyelvben szerepel az üresszó, akkor) csak az S → λ szabályban fordul elő, miközben S nem szerepel egyik szabály jobb oldalán sem (ahol S a mondatszimbólum).

Tekintsük most a nyelv üresszómentes részét, ennek megfelelően nem használunk A → λ alakú szabályt egyáltalán. Megmutatjuk, hogy az A → B alakú, úgynevezett láncszabályoktól (vagy nemterminális átnevezésektől) is meg tudunk szabadulni.

9. Definíció. Egy reguláris nyelvtanról azt mondjuk, hogy erős normálformában van, ha minden szabályára teljesül az alábbi alakok egyike: A → a B, A → a (ahol A, BN, aT). ★

21. Tétel. Minden reguláris nyelvhez van vele ekvivalens erős normálformájú reguláris nyelvtan.

Bizonyítás. Az előzőek alapján feltehetjük, hogy G=(N, T, S, H) nyelvtanunkban csak A → a B, A → a és A → B alakú szabályok vannak ( A, BN, aT) . 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) | CBH}, 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 '={A → r | ha van olyan BN hogy B → rH , rN, BU(A)}.

Ekkor G '=(N, T, S, H ') nyelvtan erős normálformájú, és ekvivalens az eredetivel. ∎

Itt jegyezzük meg, hogy a szakirodalomban előfordul, hogy a reguláris nyelvtanokat eleve csak az imént ismertetett normálformájú nyelvtanokkal definiálják; az általunk reguláris nyelvtanként definiált nyelvtanokat pedig jobblineáris nyelvtannak hívják. Ahogy láttuk ezek a nyelvtantípusok ekvivalensek egymással, így mi továbbra sem fogunk köztük különbséget tenni.

A ballineáris nyelvtanok és a jobblineáris nyelvtanok ekvivalenciáját a lineáris nyelvtanoknál tárgyaljuk (lásd Bal- és jobb-lineáris nyelvtanok ekvivalenciája).