15.2. Automaták

Az előbbiekben megmutattuk, hogyan tudunk (formális) nyelveket létrehozni, generálni. A másik fő megközelítése a nyelvek leírásának azok automatákkal történő elfogadása. Ebben a részben az alapvető automatatípusokat mutatjuk be röviden. A hagyományos automataelméletben egy automata rendelkezik egy (input) szalaggal, amin egy olvasó (Turing-gép esetén egy író-olvasó) feje van, aminek segítségével feldolgozhatja a szalagon levő szót.

15.2.1. A véges automaták

Először az automaták legegyszerűbb csoportját a véges (elfogadó) automatákat tekintjük. A véges automata áll egy véges (állapotú) vezérlőből, egy input szalagból, mely pozíciókra van osztva, s minden egyes pozíció egy-egy betű tárolására képes, valamint egy olvasófejből, amellyel az input elejéről indulva olvassa azt betűnként.

Formálisan a következőképpen definiáljuk.

26. Definíció. Egy A = (Q, T, q0, δ, F) rendezett ötöst véges automatának nevezzük, ahol

  • Q az állapotok véges, nemüres halmaza,

  • T a bemenő- (vagy szalag-) ábécé,

  • q0Q a kezdőállapot,

  • δ az állapotátmenet-függvény,

  • FQ pedig a végállapotok vagy elfogadó állapotok halmaza.

A δ leképezés alakja alapján beszélhetünk

  • nemdeterminisztikus üresszó átmenetet is megengedő automatáról: δ : Q × (T ∪ {λ}) → 2Q (vagyis a Q halmaz lehetséges részhalmazaiba képez),

  • nemdeterminisztikus üresszó átmenet nélküli automatáról: δ : Q × T → 2Q,

  • (parciális) determinisztikus automatáról: δ : Q × TQ (parciális függvény),

  • teljesen definiált determinisztikus automatáról: δ : Q × TQ (teljesen definiált függvény).

A véges automata konfigurációja (u,q) rendezett pár, ahol uT* az inputszó még feldolgozandó része, qQ pedig az automata aktuális állapota. A kezdő konfiguráció (w,q0), ahol w az inputszó. Akkor mondjuk, hogy egy (bu,q) konfigurációból közvetlenül elérhető egy (u,p) konfiguráció (jelekkel: (bu,q) ⊢ (u,p)), ha p ∈ δ(q,b) (illetve, determinisztikus esetben p = δ(q,b)). A közvetlen elérhetőség reflexív és tranzitív lezárásával kapjuk az elérhetőség (jelekkel: ⊢*) fogalmát. Az A automata (egy futással) elfogad egy w szót, ha (w,q0) ⊢* (λ,p) valamely pF állapotra. Az elfogadott szavak halmaza adja az automata által elfogadott (vagy felismert) nyelvet.

Véges automatákat legegyszerűbben grafikusan, a gráfjukkal adhatunk meg. Az állapotoknak a gráf csúcsai felelnek meg (bijektív módon): minden egyes csúcs (körökkel jelöljük az ábrákon) meg van címkézve egy állapottal (az állapot nevét beírhatjuk a körbe). Az átmeneteket a gráf (irányított) élei jelentik: a csúcsokból kivezető minden irányított él (mely hurokél is lehet) pedig meg van címkézve egy bemenő ábécébeli jellel. Az élek, valamint azok címkéi adják meg, hogy egy adott állapotból egy adott bemenő jel hatására az automata melyik állapotba megy át: a bemenőjeleket az élek címkéi, az állapot átmeneteket pedig az élek kezdő- és végcsúcsainak címkéi adják meg. A kezdőállapotot külön megjelöljük egy bemenő nyíllal (ami nem másik állapotból mutat ide). Az elfogadóállapotokat pedig dupla körvonallal szokás jelölni.

A következő eredmény Kleene nevéhez kötődik.

30. Tétel. A véges automaták osztálya (bármelyik az ismertetett négy változat közül) éppen a reguláris nyelvek (REG) osztályát fogadja el.

15.2.2. A veremautomaták

A véges automatát kiegészítve egy külső verem memóriával kapjuk a veremautomata fogalmát, formálisan a következőképpen definiálhatjuk.

27. Definíció. Egy veremautomata egy rendezett hetes: A = (Q, T, Z, q0, Z0, δ, F), ahol

  • Q a belső állapotok nem üres és véges halmaza;

  • T az inputábécé, vagy szalagábécé;

  • Z a veremábécé;

  • q0Q a veremautomata kezdőállapota;

  • Z0Z a kezdő veremszimbólum (más terminológiával a verem alja);

  • δ a (nemdeterminisztikus) átmenetfüggvény: leképezés a Q × (T ∪ {λ}) × Z-ből a Q × Z* véges részhalmazaiba;

  • FQ a veremautomata végállapotainak halmaza.

Egy veremautomata pillanatnyi konfigurációján értjük azt az (u, q, z) hármast, ahol uT* az input még fel nem dolgozott része, zZ* a veremmemória pillanatnyi tartalma (z első betűje a verem tetején, utolsó betűje pedig a verem alján lévő betű), qQ pedig a veremautomata pillanatnyi belső állapota. Egy veremautomata minden lépésben a pillanatnyi konfigurációból a δ átmenetfüggvény definíciója értelmében egy vagy több pillanatnyi konfigurációba mehet át (vagy épp nem mehet át egybe sem). Az átmenet történhet oly módon, hogy közben a veremautomata nem kéri a bemenő jelsorozat következő jelét (λ-lépés). Az A veremautomata egy (au, q, Xz) ∈ (T* × Q × Z+) konfigurációt egy lépésben átalakít az (u, p, tz) ∈ (T* × Q × Z*) konfigurációba, ahol a ∈ (T ∪ {λ}), XZ pedig a verem tetején levő szimbólum, (jelekben: (au, q, Xz) ⊢ (u, p, tz), ha van olyan aT ∪ {λ}, p, qQ, valamint tZ*, hogy a következő összefüggés fennáll: (p, t) ∈ δ (q, a, X). Az (u, q, z) ⊢* (v, p, t) relációt (A véges sok lépésben átalakít) areláció reflexív és tranzitív lezárásával kapjuk. A veremautomata által (végállapottal) elfogadott nyelv:

L(A)f = {wT* ∣ (w, q0, Z0) ⊢* (λ, p, z) valamely zZ*, pF esetén}.

Üres veremmel elfogadott nyelv:

L(A)v = {wT* ∣ (w, q0, Z0) ⊢* (λ, p, λ) valamely pQ esetén}

(Itt jegyezzük meg, hogy az üres veremmel történő elfogadáshoz nincs szükség végállapotra.)

Habár a kétféle elfogadási mód teljesen más működést feltételez, az elfogadható nyelvek szempontjából ekvivalens működési modellekről van szó.

31. Tétel. A nemdeterminisztikus veremautomaták éppen a a környezetfüggetlen nyelvek (CF) osztályát fogadják el végállapottal. A nemdeterminisztikus veremautomaták éppen a a környezetfüggetlen nyelvek (CF) osztályát fogadják el üres veremmel.

Sőt, minden környezetfüggetlen nyelv elfogadható olyan veremautomatával, amely üres veremmel és végállapottal is az adott nyelvet fogadja el.

Ezen kívül megmutatható, hogy a veremautomatákban az állapotok sokkal kisebb jelentőséggel bírnak, mint a verem: Minden környezetfüggetlen nyelvhez van olyan egy állapottal rendelkező veremautomata, ami az adott nyelvet fogadja el (természetesen, így üres veremmel).

Megemlítjük még, hogy a determinisztikus veremautomaták kisebb nyelvosztályt tudnak elfogadni, a végállapottal elfogadó determinisztikus veremautomaták által elfogadott nyelvosztályt szokás determinisztikus környezetfüggetlen osztálynak nevezni.

Az egyfordulós veremautomaták speciális működésű veremautomaták, amelyekben a verem tartalma egy ideig nő, aztán pedig csak csökkenhet. Vagyis a számítás első részében mindig legalább egy veremszimbólum kerül a verembe (a kivett helyett, ennek megfelelően nem csökkenhet a verem tartalmának mérete), aztán viszont a számítás második részében már csak csökkenhet a veremtartalom. Tehát nem fordulhat elő (semmilyen inputon dolgozva), hogy ha már egyszer egy átmenet olyan volt, hogy a veremből kivett szimbólum helyett nem került be semmi (vagyis a verem tartalma csökkent ebben a lépésben), akkor megint egynél több szimbólum kerüljön be a verembe egy lépésben. (Csak a kivett szimbólum helyére kerülhet valami, vagy csak törlünk a veremből.)

A nemdeterminisztikus egyfordulós veremautomaták éppen a lineáris nyelveket (LIN) fogadják el a Chomsky-hierarchiában. A determinisztikus egyfordulós veremautomaták egy kisebb nyelvosztályt tudnak elfogadni, ezeket a nyelveket szokás determinisztikus lineáris nyelveknek hívni.

Most egy általános célú automatát, a Turing-gépet mutatjuk be, illetve a kiszámíthatóság fogalmának átnézése következik. A Turing-gépet Alan Turing 1936-ban vezette be automatikusan végrehajtható számítási eljárások tanulmányozására, annak a mintájára, ahogy egy hivatalnok dolgozik. Egyszerűsége ellenére a modell jól használható a hagyományos elektronikus számítógépek számítási kapacitásának elvi korlátainak kutatásában.

15.2.3. A Turing-gép

A Turing-gép egy absztrakt „szekvenciális hozzáférésű'' számítási modell, amit a számítástudomány ma is használ, ez a számítások tulajdonságainak feltárásához leggyakrabban használt elméleti modell.

A Turing-gép egy potenciálisan végtelen szalagmemóriával és egy író-olvasó fejjel ellátott véges állapothalmazzal rendelkező automata. A szalagmemória pozíciókra van osztva, s minden egyes pozíció mint memóriaegység a szalagábécé pontosan egy betűjének tárolására képes. Kezdetben a Turing-gép egy előre specifikált kezdőállapotában van, s a szalagon egy véges hosszúságú input szó helyezkedik el. A Turing-gép szekvenciális működésű: működésének kezdetekor a Turing-gép író-olvasó feje az input szó első betűjén áll. Az input szó előtti és utáni (végtelen sok) szalagpozíció egy speciális betűvel, a szóközzel (üres betűvel), ami nem egyezik meg az üresszóval(!), van feltöltve. Hogy az input szó elkülöníthető lehessen a szalag többi részén tárolt mindkét irányban végtelen számú szóköztől, feltételezzük, hogy az input szó nem tartalmaz szóközt. Az input szó tehát az író-olvasó fej alatti betűtől (jobbra haladva) a szalag utolsó nem üres betűjéig tart. Speciálisan, üres input szó is elképzelhető. Ez esetben a szalag minden egyes pozíciója szóközzel van feltöltve, és az író-olvasó fej ezek egyikére mutat. (Utolsó szóköztől különböző betű pedig ekkor értelemszerűen nincs.) A Turing-gép diszkrét időskála mentén, elkülönített időpillanatokban hajt végre egy-egy elemi műveletet, mely az író-olvasó fej alatti betű olvasásából, ezen betű felülírásából, a belső állapot változtatásából, s az író-olvasó fej egy pozícióval való balra avagy jobbra mozgatásából, vagy éppen a fej helybenhagyásából áll. Amennyiben a Turing-gép eljut egy végállapotba, megáll.

A gép a szalagról olvashat, és arra írhat is. A Turing-gép szalagja végtelen, s mivel ezen bármilyen irányban tudja a fejet mozgatni, a gép (külső-, vagyis szalag-)memóriája elvileg végtelennek tekinthető.

Formálisan a következőképpen definiálhatjuk a Turing-gépet.

28. Definíció. Az M = (Q, T, V , q0, #, δ, F) rendezett hetest Turing-gépnek nevezzük, ahol

  • Q = {q0, q1, ..., qn} a belső állapotok véges halmaza;

  • T = {a1, a1, ..., am} az input ábécé, az input pedig valamely wT* szó;

  • V a szalagjelek véges halmaza, VT, ezek mind az input, mind az output, illetve a részeredmények megadására szolgáló jelek beleértve a # ∈ V szóköz betűt is, viszont # ∉ T;

  • q0Q kezdőállapot;

  • FQ a végállapotok halmaza;

  • míg a δ a gép átmenet-, vagy mozgásfüggvénye, ami az aktuális állapot és az aktuális szalagpozíción levő jel alapján megmondja, hogy a gép mire írja át (vagy éppen ne írja át) az aktuális szalagpozíciót, mi legyen az (új) állapota, illetve a fej merre lépjen (jobbra, vagy balra), vagy helyben maradjon-e a szalagon.

Ha

δ : Q × V → Q × V × {Bal, Jobb, Helyben},

akkor kapjuk a determinisztikus Turing-gép fogalmát; ha viszont

δ : Q × V → 2Q × V × {Bal, Jobb, Helyben},

vagyis a δ a Q × V halmazból a Q × V × {Bal, Jobb, Helyben} halmaz lehetséges részhalmazaiba képez, akkor pedig nemdeterminisztikus Turing-gépről beszélünk. A definícióból kitűnik, hogy a determinisztikus Turing-gép a nemdeterminisztikusnak speciális esete (ahol a képhalmaz maximum egyelemű halmazokból áll).

Eredetileg a Turing-gép a q0 állapotban van, és az író-olvasó feje a bemeneti szó első betűjére mutat (vagyis a szalag legbaloldalibb nem # elemére), ezt hívjuk az inputhoz tartozó kiindulási konfigurációnak. A Turing-gép működése a következő:

Ha tehát az M Turing-gép egy qQ állapotban van és az író-olvasó fej alatt valamely aV jel áll, akkor a (q',b,L) ∈ δ (q,a) hármas szolgáltatja a gépnek a műveleti lépés végrehajtása utáni új q' állapotát, az a szalagjelet felülíró b szimbólumot (mely nem feltétlen különböző a felülírt szimbólumtól), illetve az elmozdulás LBal, Jobb, Helyben irányát. Az L a következőt jelenti: Bal esetén a Turing-gép író-olvasó feje egyet balra lép; Jobb esetén a gép feje egyet jobbra lép; Helyben esetén pedig nem mozdítja az olvasó-író fejet a gép.

A nemdeterminisztikus esetben a δ(q,a)-beli rendezett hármasok egyike szolgáltatja (bármelyike szolgáltathatja) az új állapotot, az új szalagjelet, illetve a mozgás irányát.

Abban az esetben, ha δ(q,a) = ∅, azt úgy interpretáljuk, hogy ha a gép a q állapotban az író-olvasó fej alatt az a betűt találja, további működését felfüggeszti (megáll). Eredményt viszont csak akkor szolgáltat, ha végállapotban áll meg a gép (ezt hívjuk végkonfigurációnak).

Megjegyezzük, hogy bár a gép szalagját mindkét irányban végtelennek tekintjük, minden időpillanatban csak véges sok #-tól különböző jel lehet rajta.

A Turing-gépeknek számos változata ismert.

Megadhatunk olyan Turing-gép változatot, ahol a fej csak a Bal és Jobb irányokba léphet, és nem maradhat Helyben. Belátható, hogy egy ilyen Turing-gép szimulálni tudja az eddigiekben ismertetett változatnak a fejet helyben hagyó lépéseit is: pl. egyet balra lép a fej, és egy olyan állapotba kerül az automata, amiben bármit is olvas a szalagon, azt nem változtatja meg, viszont jobbra visszalép és az eredeti automata állapotának megfelelő állapotba kerül.

Ugyancsak szokásos a csak egyirányban végtelen szalagú Turing-gép használata, amelyik szintén képes az általános változat szimulációjára. Ekkor a szalag első karaktere egy speciális jel, amiből a gép rájön, hogy erre nem mehet tovább a fej. Ekkor egy olyan speciális állapotba kerül, aminek hatására jobbra lép, először leírja azt a jelet, ami eredetileg a speciális szimbólum helyére írt volna (ha a szalag mindkét irányban végtelen lenne), majd az itt olvasott karaktert eggyel jobbra, és így tovább, vagyis a szalag teljes (értelmes) tartalmát eggyel jobbra másolja, ezután (észlelve a felhasznált tárterület jobb szélét), a fej vissza mozog a baloldalra, ahol a gép folytatja az eredetileg tervezett számítását.

Megkülönböztethetünk kiszámító és eldöntő Turing-gépeket a következő definíció alapján.

Amennyiben a Turing-gép célja adott függvény kiszámítása a megadott bemenő értékekkel, akkor a gép a megállásakor az (output)szalagon a megfelelő eredményt hagyja. Ezzel szemben vannak olyan számítások, amikor a választ egy igen-nem kérdésre keressük, ezesetben eldöntő vagy elfogadó Turing-gépről beszélünk. Ilyen Turing-gépekkel lehet pl. egy L nyelvet elfogadtatni a következőképpen: bemenet egy wT* szó, a Turing-gép számításának eredménye pontosan akkor „igen'' ha wL teljesül. (Hasonló módon szokás azokat az input szavakat elfogadni, amelyekre a számításokat az elfogadó állapotban fejezi be a gép.)

A nemdeterminisztikus Turing-gépek esetén az elfogadást úgy definiáljuk, hogy van olyan számítási sorozat az adott inputra, amely az elfogadó eredményt szolgáltatja. Érdekes módon a determinisztikus Turing-gépekkel pontosan azok az eldöntési feladatok oldhatóak meg, amelyek a nemdeterminisztikus Turing-gépekkel.

A Church-Turing tézis értelmében egy igen/nem problémaosztályt megoldhatónak hívunk, ha létezik olyan rögzített algoritmus (Turing-gép), mely az osztály tetszőleges problémája, mint bemenő adat esetén, eredményként megadja a helyes „igen'' vagy „nem'' választ. 1936-ban Turing azt az akkor meglepő eredményt bizonyította, hogy létezik ebben az értelemben megoldhatatlan feladatosztály.

A kiszámíthatóság fogalma a számítástudományban másként is megjelenik: a Turing-gépekkel elfogadott nyelvek osztálya éppen a rekurzívan felsorolható nyelvek (RE) osztályával egyezik meg (akár a determinisztikus, akár a nemdeterminisztikus Turing-gépeket tekintjük). Ugyanezt a nyelvosztályt lehet generálni a Chomsky-féle generatív nyelvtanokkal (0-típusú nyelvtanok). A Turing-gép fogalma tehát szorosan összekapcsolódik a „kiszámíthatóság'' fogalmával. Turing-géppel mindent (és pont azokat a feladatokat) ki lehet számolni, amit algoritmikusan meg lehet oldani. Ezek szerint a Turing-gép a lehető legáltalánosabb számítási eszköz, azaz minden, ami effektíve kiszámítható, kiszámítható Turing-géppel is.

Akkor mondjuk, hogy egy Turing-gép valamely input szó hatására megáll (és eredményt szolgáltat), ha az input szó eleme a tekintett Turing-gép által felismert nyelvnek (elfogadó Turing-gép esetén), vagy általában, ha az input szóhoz tartozó kezdő konfigurációból kiindulva a gép eljut egy végkonfigurációba.

A Turing-gépek megállási problémája a következő: van-e algoritmus arra, hogy eldöntsük, hogy egy tetszőlegesen adott Turing-gép egy tetszőlegesen adott input szóra megáll-e. Turing tétele értelmében ez a probléma megoldhatatlan. Ez azt jelenti, hogy vannak olyan jól megfogalmazható problémák, amiknek elvileg sincs (algoritmikus) megoldása.

Szerencsére azonban rengeteg olyan probléma ismert, ami megoldható. Ezekkel kapcsolatban a következő fontos kérdés, hogy milyen hatékonyan oldhatóak meg. Ezzel a kérdéssel foglalkozik a bonyolultságelmélet, amit a következő alfejezetben tekintünk át röviden.

Előbb viszont néhány speciális típusú Turing-gépről ejtünk szót.

Először egy korlátozott modellt tekintünk, amely csak az inputhossznak megfelelő szalagméretet használhat fel a számítás során. Legyen a Turing-gép olyan, hogy a δ mozgásfüggvénye eleget tesz a

Q × (V ∖ {#}) → 2Q × V × {Bal, Jobb, Helyben}

és

Q × {#} → 2Q × {#} × {Bal, Jobb, Helyben}

feltételnek is. Láthatjuk, hogy ugyan a modell nemdeterminisztikus, nem írhatja felül a szalag üres betűit. Ez a lineárisan korlátozott automata néven ismert nemdeterminisztikus változat éppen a környezetfüggő nyelvek (CS) elfogadására képes.

Egy Turing-gép δ függvénye, és így maga a Turing-gép is végesen leírható. Egy ilyen leírást az adott Turing-gép programjának (kódjának) nevezünk. Az univerzális Turing-gép egy olyan Turing-gép, ami el tudja olvasni és végre tudja hajtani az így leírt programot: inputként megkapva a programot és az inputot amin azt végre kell hajtani, képes szimulálni az eredeti (kódolt) Turing-gép működését, és így ugyanazt az outputot szolgáltatni, amit az eredeti gép adna az adott input esetén. Az univerzális Turing-gép egy általános, elvont számítógép, ami minden Turing-gépet képes szimulálni, vagyis elvileg a programjának megfelelően képes feldolgozni az input szót. Ez azt jelenti, hogy van olyan gép, ami minden kiszámítható függvényt ki tud számolni. Az ilyen univerzális gépek létezésének bizonyítása, illetve megkonstruálásuk nagyban hozzájárult az általános célú számítógépek megjelenéséhez.