4. fejezet - A véges automaták elméletének alapjai

Ebben a fejezetben a véges automaták elméletébe nyújtunk betekintést.

4.1. Az automata fogalma és főbb típusai

Automatán egy olyan absztrakt rendszert fogunk érteni, mely egy diszkrétnek képzelt időskála időpillanataiban érkezett ingerek hatására ezen időpillanatokban válasszal reagál, miközben belső állapotát megadott szabályok szerint változtatja a külső ingerek hatására. Az ingerekre adott válasz függ mind az ingerektől mind pedig a pillanatnyi belső állapottól. Ebben az értelemben tehát nemcsak a gépek, hanem bármiféle élő vagy élettelen objektumok tekinthetők automatának, ha ezen séma szerint vizsgáljuk őket, azaz ilyenfajta működést tulajdonítunk nekik.

4.1. példa - Automaták

A legkülönbözőbb létező vagy nem létező dolgok tekinthetők automatának. Automatának tekinthető a lakásunk ajtaja, ablaka. Bizonyos értelemben automatának tekinthető a kedvenc macskánk, a számítógépünk, vagy a lakáscsengőnk is. Vizsgálhatjuk a főnökünket is mint automatát, hisz minden bizonnyal különféleképp reagál arra, hogy az elvárásainak megfelelően cselekszünk-e vagy sem. (És az is valószínű, hogy ezek a dolgok a főnök állapotát is befolyásolják.) De automatának tekinthető az inkák esőistene, aki imádságra esővel, káromkodásra szárazsággal reagál. ★


Azon automatákat amelyek egy inputszóhoz egy output szót rendelnek a működésük folyamán, átalakítóknak, transzduszereknek is szokás nevezni. A következőkben főleg ilyenekkel fogunk foglalkozni, szemben a későbbi részekben előtérbe kerülő elfogadó automatákkal.

4.1.1. Mealy automata

Az absztrakt automaták egyik nevezetes típusa a Mealy (ejtsd: míli) automata. Mealy automatán fogunk érteni egy A=(Q, T, V, d, f) ötöst, aholis Q a (belső) állapotok nem üres halmaza, T a bemenő jelek nem üres halmaza, V a kimenőjelek nem üres halmaza, d:Q×T  → Q az átmeneti függvény és f:Q×T  → V a kimeneti függvény.

Úgy képzeljük, hogy a Mealy automata diszkrét időskála mentén működik, s annak minden egyes időpillanatában egy-egy jól meghatározott állapotban van. Ha valamely időpillanatban egy A=(Q, T, V, d, f) Mealy automata egy qQ állapotában az aT bemenő jelet kapja, akkor ugyanezen időpillanatban a f(q, a) kimenőjellel reagál, majd a következő időpillanatra átmegy a d(q, a) állapotba.

4.1.2. Moore automata

Amennyiben az A=(Q, T, V, d, f) Mealy-automatához létezik olyan g:Q → V függvény, hogy tetszőleges qQ állapota és aT bemenő jele esetén teljesül a f(q, a)=g(d(q, a)) egyenlőség, akkor Moore-automatáról beszélünk. A Moore-automatát A=(Q, T, V, d, g) alakban szokás megadni, ahol g:Q → V a Moore-automata jelfüggvénye. Tetszőleges qQ állapot esetén azt mondjuk, hogy g(q) a qQ állapotjele.

A Moore automata a diszkrét időskála minden egyes időpillanatában egy-egy jól meghatározott qQ állapotban van (amikor az állapotjele g(q)). Ha egy adott időpillanatban ezen qQ állapotában az aT bemenő jelet kapja, akkor a következő időpillanatban d(q, a) lesz az állapota, s állapotjele pedig g(d(q, a)) lesz. Ily módon a Moore-automata egy adott időpillanatban kapott bemenő jel hatására a következő időpillanatra átmegy ezen bemenő jel és a belső állapota által egyértelműen meghatározott állapotba, s ezzel egyidejűleg kiadja az új állapot által egyértelműen meghatározott állapotjelet.

Képletesen szólva, amíg a Mealy-automata az olyan embert is modellezheti, aki először cselekszik, azután gondolkodik, addig a Moore-automata az olyan embert modellezi, aki először gondolkodik azután cselekszik.

4.1.3. Kimenőjel nélküli automata

A Moore-féle automata a Mealy-féle automata speciális eseteként adódik. A Moore-féle automata további specializálásával jutunk el a kimenőjel nélküli automata fogalmához a következő módon. Amennyiben egy A=(Q, T, V, d, g) Moore-automatára Q=V és g:Q → Q egy identikus leképezés (azaz minden qQ- ra g(q)=q), akkor a kimenőjel nélküli automata fogalmához jutunk. Figyelembe véve azt a tényt, hogy a Moore-automatát egy olyan A=(Q, T, V, d, f) Mealy-automatából származtatjuk, melyhez található olyan g:Q → V függvény, hogy egy tetszőleges qQ, aT pár esetén f(q, a)=g(d(q, a)), továbbá figyelembe véve, hogy a kimenőjel nélküli automata olyan Moore-automata, melynek a jelfüggvénye identikus leképezés, azt is mondhatjuk, hogy a kimenőjel nélküli automata egy olyan A=(Q, T, V, d, f) Mealy-automata, melyre Q=V és d=f. Ezen okok miatt a kimenőjel nélküli automatát A=(Q, T, d) alakban szokás megadni.

Egy A=(Q, T, d) kimenőjel nélküli automata esetén a T bemenő jelhalmaz miden aT eleme egy olyan a:Q → Q egy változós műveletnek (vagyis Q önmagába történő leképezésének) is tekinthető, mely az állapothalmaz tetszőleges qQ eleméhez az a(q)=d(q, a) elemét rendeli. Univerzális algebrai kifejezéssel élve tehát a kimenőjel nélküli automaták unoidok, vagy más szóval unáris algebrák. Ez az egyszerű felismerés lehetővé teszi számunkra a modern algebra módszereinek automataelméleti alkalmazását.

Amint láttuk, a Moore-féle automata speciális Mealy-automataként definiálható. Később látni fogjuk, hogy ez a specializáció látszólagos, ugyanis információ átalakítás szempontjából a két fogalom ekvivalens. (Az információ átalakításán azt értjük, hogy az automata tetszőleges bemenő információ hatására valamilyen "kimenő" információval reagál.) Nevezetesen, absztrakt szempontból a Mealy és a Moore-féle automaták ekvivalensek egymással abban az értelemben, hogy már a speciálisabb Moore-automatákkal előállíthatók azok az információ átalakítások, amelyek Mealy automatákkal megvalósíthatók. Tehát a Moore-automata ebből a szempontból csak látszólag speciálisabb a Mealy-automatánál.

Később látni fogjuk azt is, hogy az elmélet kiépítésénél sok esetben elegendő kimenőjel nélküli automatákra szorítkozni.

Az említett három automata típus mindegyike esetén szokás véges automatáról beszélni, ha az állapothalmaz, a bemenő jelhalmaz, s a kimenő jelhalmaz végesek. Szokás véges állapotú automatáról vagy Q- véges automatáról beszélni, ha az állapothalmaz véges. Hasonló értelemben beszélünk véges bemenetű vagy T- véges, illetve véges kimenetű vagy V- véges automatáról, valamint (Q, T)-, (Q, V)-, illetve (T, V)- véges automatáról.

4.1.4. Iniciális automata

Amennyiben az említett automata-típusok valamelyikénél kijelölünk egy q 0 iniciális-, vagy más néven kezdőállapotot, s feltételezzük, hogy az automata működésének van egy kezdő időpontja, amikor az automata ebben az állapotban van, akkor iniciális automatáról beszélünk. Az iniciális Mealy-féle automatát A=(Q, T, V, q 0, d, f) alakban, az iniciális Moore-féle automatát A=(Q, T, V, q 0, d, g) alakban, illetve az iniciális kimenőjel nélküli automatát A=(Q, T, q 0, d) alakban szokás megadni, ahol mindhárom esetben q 0 az iniciális állapotot jelöli.

Az említett automatáknak szokás beszélni az alábbi általánosításairól is.

4.1.5. Parciális és teljesen definiált automata

Ha az átmeneti, illetve kimeneti függvény lehet parciális is, azaz nem teljesen definiált, akkor parciális automatáról van szó. Teljesen definiált függvényértékek esetén időnként szokás teljesen definiált automatáról is beszélni.

4.2. példa - Parciális automata

Az ajtó szigorú értelemben egy parciális kimenőjel nélküli automatának tekinthető. Bemenő jelei a csukás és a nyitás, s ennek megfelelően két állapota van, nevezetesen csukott és nyitott állapot. Csukott állapotból nyitással lehet nyitott állapotba hozni, nyitott állapotból pedig csukással lehet csukott állapotba hozni. De az ajtó valóban parciális automata, hisz nyitott ajtót kinyitni, vagy csukott ajtót becsukni nem lehetséges. ★


4.1.6. Nemdeterminisztikus és determinisztikus automata

Amennyiben az átmeneti és a kimeneti függvények (illetve Moore-automata esetén az átmeneti és a jelfüggvények) nem egyértelműen definiáltak, nemdeterminisztikus automatáról van szó. Ekkor valójában ezek nem is tekinthetőek függvénynek a hagyományos értelemben. Ahhoz, hogy matematikai értelemben mégis függvényekkel dolgozzunk úgy tekintjük őket, mintha nem az állapot-, illetve a kimenő jelhalmazba képeznének, hanem ezen halmazok összes részhalmazainak halmazaiba. Egy nemdeterminisztikus A=(Q, T, V, d, f) Mealy-automata esetén tehát az átmeneti függvény d:Q×T → 2 Q , a kimeneti függvény pedig f:Q×T → 2 V alakú, ahol 2 Q , illetve 2 V az állapothalmaz, illetve a kimenő jelhalmaz részhalmazainak halmazát jelöli. Értelemszerűen, egy nemdeterminisztikus A=(Q, T, V, d, g) Moore-automata esetén az átmeneti függvény d:Q×T → 2 Q , a jelfüggvény g:Q → 2 V alakú, míg egy nemdeterminisztikus kimenőjel nélküli A=(Q, T, d) automatánál az átmeneti függvény formája d:Q×T → 2 Q .

4.3. példa - Nemdeterminisztikus automata

Nemdeterminisztikus kimenőjel nélküli automatának tekinthető a dobókocka, melynek egyetlen bemenő jele a feldobás. Ezen bemenő jel, azaz a feldobás hatására a dobókocka a hat lehetséges állapotából átmehet a hat lehetséges állapot bármelyikébe annak megfelelően, hogy a feldobás után éppen melyik lapjára esik. ★


További változata a nemdeterminisztikus automatáknak, ha megengedjük, hogy az automata bemenő jel nélkül is állapotot váltson: d:Q×(T∪{λ}) → 2 Q . Ezeket szokás üresszóátmenetes (nemdeterminisztikus) automatáknak is nevezni.

A nemdeterminisztikus automata ellentéteként beszélünk determinisztikus automatáról is. Determinisztikus automata esetén tehát a szóban forgó függvényertékek mindig pontosan egy (parciális automata esetén maximum egy) meghatározott értéket vesznek fel. (A nemdeterminisztikus terminológiával pedig a függvények értékkészlete csak egyelemű, illetve maximum egyelemű részhalmazokat tartalmaz.) Determinisztikus automatáknál nem fordulhat elő üresszóátmenet.

Ha például egy nemdeterminisztikus A=(Q, T, V, d, f) Mealy-automata esetén a d(q, a) függvényérték a Q- nak egy hat elemű részhalmaza, f(q, a) pedig a V egy két elemű részhalmaza, akkor az A Mealy-automata a q állapotából az a bemenő jel hatására ezen hat elemű részhalmaz bármelyik elemébe átmehet, s kimenőjelként pedig az említett két elemű halmaz báremlyik elemét kiadhatja. S tekintettel arra, hogy egy halmaznak az üres halmaz is részhalmaza, az is előfordulhat, hogy valamely qQ állapotra és aT bemenő jelre d(q, a), vagy éppen f(q, a) értéke az üres halmaz. Ha d(q, a) az üres halmaz, ez annak felel meg, hogy erre az állapota és bemenő jelre nincs értelmezve egyetlen állapot sem amibe átmenet történhet, ha pedig f(q, a) az üres halmaz, akkor ez azt jelenti, hogy erre az állapota és bemenő jelre nincs értelmezve egyetlen kimenőjel sem.

Ezek szerint a parciális automata olyan nemdeterminisztikus automatának tekinthető, ahol a megfelelő függvényértékek vagy egy elemű halmazokat, vagy pedig az üres halmazt szolgáltatják, a teljesen definiált determinisztikus automata pedig egy olyan nemdeterminisztikus automata, ahol ezek a függvényértékek mindig egy elemű halmazok.

4.1.7. Sztochasztikus automata

Fontos általánosítás a valószínűségi vagy sztochasztikus automata, mikoris egy P((r, b)|(q, a)) feltételes valószínűség adja meg, hogy mi a valószínűsége annak, hogy az automata a r állapotba megy át és a b kimenőjelet adja ki azon feltétel mellett, hogy miközben a q állapotban volt, az a bemenő jelet kapta. Tehát egy valószínűségi automata A=(Q, T, V, P) alakban adható meg, ahol Q az állapotok nem üres halmata, T a bemenő jelek nem üres halmaza, V a kimenőjelek nem üres halmaza, P pedig az említett feltételes valószínűség.

4.1.8. Rabin-Scott automata

Az automaták egy fontos osztályát képezik a Rabin-Scott féle automaták (ejtsd rabinszkott), melyeket felismerő vagy elfogadó automatáknak is hívnak. A Rabin-Scott féle automata egy A=(Q, T, q 0, d, F) ötös, ahol Q a nem üres állapothalmaz, q 0Q a kezdőállapot, T a nem üres bemenő jelhalmaz, d:Q×T  → Q az átmeneti függvény, FQ pedig a végállapotok nem üres halmaza. ( q 0F megengedett, azaz előfordulhat, hogy a kezdőállapot egyúttal végállapot is.)

A bemenő jelekből felépülő véges hosszúságú láncokat bemenő szavaknak hívjuk. Bemenő szónak tekintjük a λ üresszót is, mely nem tartalmaz egyetlen betűt sem. Egy Rabin-Scott automata a λ üresszót definíció szerint akkor ismeri fel, ha q 0F. Egy nem üres, a 1, …, a n (nem feltétlenül különböző) bemenő jelekből álló a 1⋅⋅⋅a n bemenő szó esetén akkor mondjuk, hogy a tekintett A=(Q, T, q 0, d, F) Rabin-Scott féle automata felismeri, ha alkalmas q 1, …, q n állapotaira q 1=d(q 0, a 1), …, q n =d(q n-1, a n ) teljesülése mellett q n F.

Az A Rabin-Scott automata által felismert L(A) nyelvnek hívjuk mindazon bemenő szavak halmazát, melyeket az automata felismer.

Értelmezhetjük a nemdeterminisztikus felismerő automatát is. Ekkor az automata által elfogadott nyelv alatt azon w szavak halmazát értjük, amelyekre az automatának van olyan lehetséges állapot-lánca, amely a kezdőallapotból indul és végállapottal végződik, valamint az átmenetek bemenő jeleit összeolvasva éppen a w szót kapjuk.

Itt jegyezzük meg, hogy az átmenetfüggvényt szokás a d helyett a görög δ betűvel is jelölni.

4.4. példa - Rabin-Scott automata működés közben


A véges elfogadó automatákra a következő részben, a reguláris nyelvek kapcsán még visszatérünk.