Kétirányú automaták Kétirányú automata: ugyanolyan, mint az eddig megszokott véges automata, annyi különbséggel, hogy a $\delta$ átmeneti függvény egy állapotból és egy karakterbõl álló párhoz egy új állapotot és egy irányt ( $\in\{\;l,r,s\;\}$) rendel, az irány szerint lép az automata balra, jobbra vagy semerre (és persze megy át az új állapotba). Lehet nem determinisztikus is, most azonban nézzünk egyenlõre csak determinisztikusakat. Rövitítés: 2VA. Állítás: A kétirányú automaták sem erõsebbek mint az egyirányúak, azaz ugyanazokat a nyelveket ismerik fel mint az eddigi 1VA-k. 1.Az s irány, azaz a semerre-se-lépés elhagyása nem gyengíti az automatát. Ez azért igaz, mert ha van egy olyan 2VA, ami tartalmaz s-es átmenetet, akkor ehhez készíthetünk egy olyan, másik 2VA-t, ami ugyanazt fogadja el, csak nincsen benne ilyen s-es átmenet. A következõképpen megy ez: ha van egy $(P,a)\ensuremath{\rightarrow} (Q,s)$ átmenet, akkor kövessük az automata mûködését egészen addig, amíg végre lelép az a-ról. Ha ekkor R állapotba kerül és jobbra/balra lép, akkor vegyük be a $(P,a)\ensuremath{\rightarrow} (R,j/b)$ szabályt, az s-eset meg hagyjuk el. Elsõ ötlet: Szimuláljuk a 2VA-t egyirányúval a következõ módon. Amíg elõre lépked a 2VA, addig menjünk mi is vele, ha visszafele indulna, akkor mi álljunk meg és várjuk meg amíg visszatér. Ha visszatért, akkor vegyük fel mi is újra a fonalat. 2. Elõfordulhat, hogy nem tér vissza a 2VA, de akkor nem is tudja végigolvasni a szót, azaz nem fogadja el. Ez persze nem baj, ekkor mi is megállhatunk az 1VA-val és ekkor az 1VA sem fogad el. Második ötlet: Ne várjuk meg amíg visszatér (pláne, mert lehet, hogy nem is tér vissza), hanem tegyük fel, hogy valaki megmondja nekünk, hogy visszajön-e és ha igen, akkor milyen állapotban. Ha pl. a 2VA egy (R,a) párra a (Q,l) párral válaszol, tehát elindul visszafelé, akkor az a valaki megmondja nekünk, hogy ehhez az állapothoz milyen visszatérõ állapot tartozik (mondjuk ez P) és ekkor a szimulációt a P állapotból folytatuk, azaz a megnézzük, hogy a 2VA mit tesz a (P,a) párra. (Megjegyzés: ezt az információt, amit ez a valaki tud, úgy nevezzük, hogy ismerjük a visszatérési falat.) 3. Ha a (P,a) pár hatására újra visszafele indul a 2VA, akkor az elõbbi eljárást csináljuk mi is újra. Ezt nem tesszük a végtelenségig, mert csak véges sok állapotunk van. Ha ismétlõdést találunk, azaz olyan állapotot érintünk aminek a hatására már egyszer elindultunk ugyaninnen visszafele, akkor tuti, hogy most már mindig itt fogunk cikázni elõre-hátra, vagyis sose lépünk le az aktuális betûrõl, azaz sose olvassuk el a szót, tehát nem is fogadjuk el. Ha ezt a helyzetet felismertük, akkor álljunk meg az 2VA-val és utasítsuk el a szót. Ha nincs végtelen ciklus és végül azért mégis lelép elõre a 2VA arról a fránya a-ról, és eközben T állapotba megy, akkor lépjünk le mi is az 1VA-val és menjünk T állapotba. Harmadik ötlet Az aktuális visszatérési falat mi is nyilván tudjuk tartani magunknak, nem kell kérdezgetni senkit. 4. Elõször is: csak véges sok visszatérési fal lehetséges, konkrétan max. (|Q|+1)|Q|-féle, ahol |Q| az állapotok száma. Ugyanis a fal megadása azt jelenti, hogy minden állapotra (van |Q| darab) |Q|+1 lehetséges kimenet van: vagy nem jön vissza, vagy valamelyik állapotban visszajön. 5. A kezdõfal az a fal, ahol minden kimenõ állpothoz a $\dagger$ (nem)visszatérõ állapot (azaz, amikor nem jön vissza) tartozik. Ez azt jelenti, hogy ha a szalag elejérõl balra le akarna menni a 2VA, akkor hiba van, megállunk és elutasítunk. 6. Ha a 2VA egy a-n áll most és a fej mögött a ${\Delta}$ v.f. van, akkor a következõ visszatérési falat (${\Delta}'$), azaz azt, ami mögé az a-t átlépve kerülünk a következõképpen számolhatjuk ki. Minden állapotra megnézzük, hogy ha abban az állapotban lépünk visssza az új falon (${\Delta}'$) át, akkor mi történik. Hát elõször is az biztos, hogy az a-ra lépünk rá. Egyik eset: Ha az a hatására az adott állapotban elõre megyünk valami Q állapotba a 2VA-ban, az azt jelenti, hogy visszalépünk a ${\Delta}'$ falon, vagyis ekkor meghatároztuk a visszatérési állapotot: ez a Q. Másik eset: Ha az a hatására az adott állapotban visszafele mennénk, akkor meg az elõzõ fal, a ${\Delta}$, megmondja, hogy mi történik velünk a a elõtt, vagyis, hogy milyen állotban kerülünk vissza a a-ra. Ebben az állpotban újra megnézzük, hogy a 2VA mit tesz, ha elõre megy, akkor megvan a visszatérési állapot, ha hátra, akkor újra a ${\Delta}$ falat nézzük. Ha észrevesszük, hogy végtelen ciklusba kerültünk és sose jutunk vissza a ${\Delta}'$ falon, akkor az eredeti állapothoz a $\dagger$ vissza-nem-térési állapotot társítjuk. Ha nincs végtelen ciklus, akkor meg az az állapot lesz a visszatérõ, amiben végre visszalépünk. Ezt az eljárást minden állapotra megcsináljuk, így kapjuk az új falat. 7. Ezután látszik már, hogy az 1VA állapotába két dolgot kell belekódolni: az adott pillanatban milyen állapotban van a 2VA és mi az aktuális visszatérési fal, ami mögött állunk. Vagyis az 1VA állapotai $(Q_i, {\Delta}_j$ alakúak, ahol Qi a 2VA állapota, ${\Delta}_j)$ pedig egy visszatérési fal. Az 1VA kezdõállapota az $(S,{\Delta}_0)$ pár lesz, ahol S a 2VA kezdõállapota, ${\Delta}_0$ pedig a kezdõfal. Azok a $(Q_i, {\Delta}_j)$ állapotok lesznek elfogadók az 1VA-ban, ahol Qi a 2VA elfogadó állapota. Aaz 1VA $\delta$ függvényét úgy számolom ki, hogy minden elõkerülõ állapotra (az elején csak a kezdõállapot, a $(S,{\Delta}_0)$, ilyen, késõbb elõkerülnek mások is) megnézzük, hogy mi az új 1VA-s állapot, azaz mi az új 2VA-s állapot és mi az új visszatérési fal