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 Q_i 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 Q_i 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

8. Ha az eredeti 2VA nemdeterminisztikus volt, akkor is ugyanez van, csak az 1VA átmeneteinek számításakor nem csak egy lehetséges új állapot jön be, hanem esetleg több. A visszatérési fal ezeknél ugyanaz lesz, ezek az állapotok csak az első komponensben (a 2VA állapotát jelölőben) különböznek.