5.5. Nyelvek előállítása automatákban

Az automaták és az automata leképezések kapcsolatát illetően, mint már utaltunk rá, két ellentétes kérdés fogalmazható meg:

I. Ha adva van egy iniciális automata, meghatározandó az áltata indukált leképezés (analízis);

II. Ha adva van egy iniciális automata leképezés, meghatározandó legalább egy olyan iniciális automata, amely ezt a leképezést indukálja (szintézis).

A szintézis, ahogy utaltunk rá egyértelművé tehető a minimalizálás feladatával. Az analízis és szintézis akkor fogalmazható meg egzakt módon, ha megállapodunk abban, hogy mit értünk automata és automata leképezés megadásán. Ezzel kapcsolatban, amint a Automaták Analízise és Szintézise fejezetben utaltunk rá, a következő problémát kell megoldani:

0. Meg kell adnunk a véges automaták által indukálható automata leképezéseknek az automatáktól független leírását. Más szóval, keresnünk kell olyan írásmódot, amelyben el tudjuk dönteni, hogy valamely, ebben az írásmódban megadott automata leképezés indukálható-e véges automatával vagy sem. Ezek után véges automatákra az analízis és szintézis problémája így fogalmazható meg:

I'. Bármely adott véges automata esetén meg kell tudnunk adni a szóban forgó írásmódban azt a leképezést, amelyet az automata indukál;

II'. Ha ebben az írásmódban meg van adva egy véges automata által indukálható leképezés, akkor meg kell tudnunk adni legalább egy olyan automatát, mely ezt a leképezést indukálja és állapothalmaza véges.

Egy olyan leképezés megadási módszer, mely eleget tesz a 0.,I.',II.' feltételeknek, először S. C. Kleene talált 1956-ban, bevezetve a reguláris kifejezés fogalmát. A fejezet további részében az elfogadó automatákra vizsgáljuk az analízis és szintézis fogalmát, vagyis az analízis és szintézis foglamát módosítjuk és e kettős feladat megoldását kimenő jel nélküli automaták vizsgálatára vezetjük vissza. Amint láttuk, a generatív rendszerek egyik fontos típusát képezik a generatív nyelvtanok, melyek a formális nyelvek előállítására alkalmas eszközök. A formális nyelvek felismerésére viszont nem az analitikus nyelvtanokat, hanem a felismerő (Rabin-Scott) automatákat szokás alkalmazni.

Tetszőleges D F A=(Q, T, q 0, d, F) determinisztikus automata esetén akkor mondjuk, hogy wL(D F A) ha az automata a q 0Q kezdőállapotból a wT * inputszó hatására a d*(q 0, w)∈F állapotba megy át.

24. Tétel. (Kleene Tétele) Bármely adott D F A véges determinisztikus automatához és állapotai F részhalmazához meg tudjuk adni annak a nyelvnek egy reguláris kifejezését, amely D F A- ban az F halmazzal előállítható. Megfordítva, minden reguláris kifejezéshez megadható egy F A véges (felismerő) automata, amely állapotai F részhalmazával éppen a tekintett reguláris kifejezéssel leírt nyelvet fogadja el.

Kleene tételének konstruktív bizonyítását fogjuk adni a következő fejezetekben.

Azt mondjuk, hogy a T * monoidon (azaz egységelemes félcsoporton) definiált valamely ρ ekvivalencia reláció jobbkongruencia, ha minden u, v, wT * hármasra igaz, hogy u ρ vu w ρ v w. A T * monoid egy C ρ osztályozását jobbról stabilnak (vagy jobbról kompatibilisnek) hívjuk, ha a ρ reláció jobbkongruencia. Végül, a ρ relációt, illetve a C ρ osztályozást véges indexűnek mondjuk, ha véges sok osztályból áll. Analóg módon definiálható a balkongruncia és a balról kompatibilis osztályozás. Egy, a T * monoidon megadott relációt kongruenciának hívunk, ha egyidejűleg bal- és jobbkongruencia. Másként kifejezve, a T * monoidon értelmezett ρ reláció kongruencia, ha bármely u, v, w, sT *- ra u ρ vw u s ρ w v s. (Megjegyezzük, hogy természetesen u, v, w, s bármelyike lehet az üresszó.) Egy ρ kongruenciához tartozó C ρ osztályozást kompatibilisnek mondunk. Másként kifejezve, kompatibilisnek hívjuk az egyidejűleg balról és jobbról stabil osztályozást.

A véges automatákban előállítható nyelvek egy relációelméleti jellemzését adja Myhill (ejtsd: májhil) és Nerode (ejtsd: neród) tétele.

25. Tétel. (Myhill és Nerode tétele) Egy véges T ábécé feletti L nyelv akkor és csak akkor állítható elő egy véges automatában az állapotok valamely részhalmazával, ha megadható T *- nak olyan véges indexű kompatibilis C osztályozása, hogy L előáll bizonyos C- beli osztályok egyesítési halmazaként.

Bizonyítás. Mindenekelőtt megjegyezzük, hogy T *- nak az a triviális osztályozása, amelynél minden elem egymagában alkot egy osztályt, nyilván kompatibilis és egy L nyelv mindig előáll ennél az osztályozásnál bizonyos osztályok egyesítési halmazaként. Ennél fogva egy tetszőleges L nyelv esetén mindig van olyan kompatibilis osztályozása T *- nak, hogy az L előáll bizonyos osztályok egyesítési halmazaként.

A tétel szükségességének bizonyításához tegyük fel, hogy egy L nyelv előállítható a D F A=(Q, T, q 0, d, F) véges automata állapotainak F részhalmazában, vagyis D F A Rabin-Scott automata éppen az L nyelvet ismeri fel. Definiáljunk T *- on egy kongruenciát a következőképp:

u, vT *:(u ρ D F A v⇔∀qQ:d *(q, u)=d *(q, v)).

(Vagyis minden u, vT * esetén u ρ D F A v akkor és csak akkor teljesüljön, ha tetszőleges Q- beli állapotra az u szó a q állapotot ugyanabba az állapotba viszi át mint a v szó.) Ekkor a ρ- hoz tartozó C ρ kompatibilis osztályozásnál egy-egy osztályba pontosan azok a T *- beli elemek tartoznak, melyek a D F A automata kezdőállapotát egy meghatározott állapotba viszik. Nyilvánvaló, hogy a D F A végessége miatt a Q halmaz véges, azaz a C ρ kompatibilis osztályozás véges sok osztályt tartalmaz. Tehát C ρ valóban véges indexű.

Azt kell még kimutatnunk, hogy L előáll bizonyos C ρ - beli osztályok egyesítési halmazaként. Jelölje most tetszőleges qQ mellett C (q) ezen C ρ kompatibilis osztályozás azon osztályát, melynek elemei a q 0 kezdőállapotot a q állapotba viszik át. Mivel feltettük, hogy a D F A az L nyelvet állapotainak F halmazával ismeri fel, ekkor L=∪{C (q)|qF}. (Természetesen L=∅ előfordulhat. Ilyen esetben F=∅.) Ezzel a tétel szükségességét kimutattuk.

Most igazoljuk az elegendőséget. Tegyük fel, hogy megadható T *- nak olyan véges indexű kompatibilis C osztályozása, hogy L előáll bizonyos C- beli osztályok egyesítési halmazaként. Korábbi konvenciónknak megfelelően tetszőleges uT * mellett C[u]- val fogjuk jelölni azt az osztályt, melynek egy adott uT * eleme. Ha L=∅, akkor L bármely véges automatában előállítható a végállapotok üres halmazával. Így a továbbiakban feltehetjük, hogy L nem üres. Mivel C kompatibilis, ez azt jelenti, hogy tetszőleges u, vT * mellett C[u]=C[v]⇒∀aT:C[u a]=C[v a] (vagyis tetszőleges u, vT * esetén a u és a v egy osztályba esése azt eredményezi, hogy minden aT esetén az u a és a v a is egy osztályba fognak esni.) Ekkor viszont jól definiált (azaz az értelmezési tartomány minden elemének valóban pontosan egy elem felel meg az értékkészletben) az a d:C×TC leképezés, melyre minden uT *, aT pár mellett d(C[u], a)=C[u a]. Tekintsük most az ezen d átmeneti függvénnyel rendelkező D F A=(C, T, C[λ], d, F) véges automatát (ahol C[λ] jelöli a C azon osztályát, mely az üresszót tartalmazza); és F jelöli a C azon részhalmazát, melyre teljesül, hogy az L előáll a F- beli osztályok egyesítéseként. A D F A definíciója értelmében minden uT *- ra d(C[λ], u)=C[u]. Világos, hogy ekkor minden uT * esetén C[u]∈C ' pontosan akkor áll fenn, ha C[λ]- t az u szó a D F A automatában valamely C '- beli állapotába viszi át. Vagyis D F A állapotainak F részhalmazával épp az L nyelvet ismeri fel. Ezzel a tétel bizonyítását befejeztük. ∎

Valamely A=(Q, T, q 0, d) kimenő jel nélküli (nem feltétlenül véges) automata esetén a ∀u, vT *:(u ρ A v⇔∀qQ:d *(q, u)=d *(q, v)- val definiált ρ kongruenciát az A Myhill-Nerode féle kongruenciájának hívjuk, a hozzá tartozó T *ρ fakorfélcsoportot pedig az A automata karakterisztikus félcsoportjának nevezzük.

Az A karakterisztikus félcsoportja nyilván úgy is megadható, mint a Q állapothalmaz feletti teljes transzformáció félcsoport azon részfélcsoportja, amelyet az összes, a d a (q)=d(q, a), qQ összefüggésnek eleget tevő d a :Q  → Q leképezések {d a |aT} halmaza generál. Ilyen interpretációban az S(A) elemei azok az η u :Q  → Q, uT * alakú leképezések lesznek, melyekre η u (q)=d *(q, u), qQ.

5.42. példa - Egy véges automatával nem felismerhető nyelv

Az L={a m b n |m>n ≥ 0} nyelv véges (kimenő jel nélküli iniciális) automatában nem állítható elő. ( a n egy n hosszúságú, csupa a betűből álló szót jelöl.) Valóban, ha L véges kimenő jel nélküli iniciális automatában előállítható lenne, akkor a Myhill-Nerode tétel szerint lenne a T *- nak véges indexű olyan C kompatibilis osztályozása, hogy L előáll véges sok osztály egyesítéseként. Mivel L végtelen elemű, s véges sok osztály egyesítéseként előáll, van olyan osztály, mely valamely i-j>k-l>0 feltételnek eleget tevő i, j, k, l természetes számokra a i b j - t és a k b l - t tartalmazza. Viszont a i b j+k-l (=a i b j b k-l )∈L, s ugyanekkor a k b k (=a k b l b k-l )∉L. Vagyis van olyan uX *, hogy a i b j uL mellett a k b l uL. Mivel feltételezésünk szerint L előáll (véges sok) C- beli osztály egyesítéseként, L- nek azok és csak azok az osztályok lehetnek a részhalmazai, melyek egyesítéseként L előáll. Ez viszont azt is jelenti, hogy a i b j u és a k b l p nem tartozhatnak a C osztályozás egy és ugyanazon osztályába. Tehát, feltételezésünknek ellentmondva a C nem kongruencia osztályozás. Ekkor viszont nem lehet az L nyelvet véges kimenő jel nélküli iniciális automatában előállítani. ★


Itt jegyezzük meg, hogy a Myhill-Nerode tétel és a nyelvet elfogadó minimális (véges determinisztikus teljesen definiált) automata szoros kapcsolatban állnak egymással. Ugyanis a bizonyításban előállított D F A éppen az L nyelvhez tartozó minimális (állapotszámú) teljesen definiált automata. Itt hívjuk fel a figyelmet arra a nagyon fontos tényre, hogy a teljesen definiált minimális determinisztikus automata (az állapothalmaz izometriájától eltekintve) egyértelműen definiálható minden reguláris nyelvhez. Ez alapján lehet eldönteni, hogy két reguláris nyelv megegyezik-e egymással.