Kétirányú véges automaták Kétirányú automata: (rövidíteni 2VA-nak fogom) 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). Az elfogadás feltétele, hogy az automata olvassa végig a bemeneti szót (azaz lépjen le jobbra az utolsó betûrõl is, ekkor szükségképpen megáll) és az az állapot, amiben megáll, legyen elfogadó. Ha az automata a szalag elején balra menne, akkor belesik a szakadékba, vagyis ekkor hibával megáll. Lehet nem determinisztikus is egy 2VA, mi most azonban feltesszük, hogy determinisztikus. (A nemdeterminisztikus eset hasonlóan menne, ezt gondoljátok meg magatoknak). Állítás: (ezt akarjuk belátni) 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_1,a)\ensuremath{\rightarrow} (p_2,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 a 2VA eközben a $(p_1,p_2,\ldots,p_t)$ állapotokat érintette és az utolsó állapotban, pt-ben jobbra vagy balra lépett, akkor vegyük be a $(p_1,a)\ensuremath{\rightarrow} (p_t,j/b)$ szabályt, az s-eseket meg hagyjuk el. Ha $t\geq \vert Q\vert+1$, akkor biztos van ismétlõdés az állpotsorozatban, tehát végtelen ciklusba kerültünk. Ekkor a (p1,a) pár hatására menjünk csapda állapotba. Ötlet: (Az állítás bizonyításához) A 2VA-t egy egyirányúval fogjuk szimulálni a következõ módon. Azt akarjuk, hogy az egyirányú automata csak azokat a mozgásait utánozza a 2VA-nak, amik elõre visznek. Ezt egyszerû megtenni, ha a 2VA $\delta$-jában egy (p1,a) párra (r1,j) van. Ekkor az 1VA p1-bõl menjen r1-be a hatására. Bonyolultabb a helyzet, ha a 2VA visszafele megy, azaz ha a (p1,a) párra (r1,b) van. Minket az igazából nem érdekel, hogy mit tesz pontosan a 2VA, amikor visszafele mászkál, csak az a fontos, hogy visszajön-e oda, ahonnan elindult hátra (jelen esetben erre a a-ra) és ha igen, akkor milyen állapotban. (Az elfogadáshoz csak az számít, hogy végigolvassa-e a szót és hogy milyen állapotba kerül a végén.) Ezt az infót egy visszatérési falnak nevezett táblázat megadja nekünk, amirõl majd látni fogjuk, hogy feltehetõ, hogy ismert. A 2VA minden helyzetéhez tartozik majd egy visszatérési fal. Ez a visszatérési fal a következõt jelenti: a 2VA minden állapotára megmondja, hogy ha az adott helyzetben visszafele indulunk az adott állapotban, akkor visszatérünk-e és ha igen, milyen állapotban. Ha van |Q| darab állapot a 2VA-ban, akkor legfeljebb (|Q|+1)|Q| darab visszatérési fal lehetséges, hiszen ennyi lehetõség van arra, hogy a |Q| soros táblázatot kitöltsük. (A +1 amiatt van, hogy lehet, hogy nem jövünk vissza, ezt $\dagger$-tel jelöljük.) Mindjárt látjuk, hogy az 1VA tudja szimulálni a 2VA mozgásait, ha az állapotaiba belekódoljuk a 2VA állapotát és az aktuális visszatérési falat. Vagyis az 1VA egy állapota egy $(p,\Delta)$ alakú pár lesz, ahol p egy 2VA állapot, $\Delta$ meg egy fal. A 2VA minden helyzetének egy 1VA állapot felel meg. Ezen infókból ( $(p_1,\Delta)$ típusúak) a következõképpen lehet meghatározni az 1VA átmeneteit. Itt azt írom le, hogy hogyan jön ki, hogy mi lesz az 1VA-ban az $(p_1,\Delta)$ állapothoz és a karakterhez tartozó új állapot. (a) Ha a 2VA elõre megy, azaz a (p1,a) párra (r1,j) van, akkor az 1VA-ban a $(p_1,\Delta)$ állapotból $(r_1, \ldots )$ állapotba megyünk. (A $\ldots$ azt jelöli, hogy még nem tudjuk, mi lesz az új fal, de az állapot biztos r1. Az új fal meghatározásáról késõbb.) Ha a 2VA hátra megy, azaz a (p1,a) párra (r1,b) van, akkor megnézzük a $\Delta$ falat, hogy mi tartozik benne az r1-hez, azaz, hogy ha r1-ben indulunk vissza, akkor milyen (2VA) állapotban érünk vissza. Ha a fal azt mondja, hogy nem érünk vissza, akkor felveszünk egy csapda állapotot az 1VA-ban és ez lesz az $(p_1,\Delta)$ állapothoz és a karakterhez tartozó új állapot. (Ez ugyanúgy mûködik, mint a sima VA-nál: elutasító állapot, ahol bármit olvasva önmagába jutunk.) Ha a fal azt mondja, hogy visszatérünk r2 állapotban, akkor ez azt jelenti, hogy r2 állapotban állunk ugyanazon az a-n, ahol kezdtük és az aktuális fal még mindig a $\Delta$. Most ugyanazt csináljuk az $(r_1,\Delta)$ párral, amit $(p_1,\Delta)$-val tettünk. Ha a $\Delta$ fal r1-re nem ad visszatérõ állapotot, akkor csapda, ha ad (mondjuk r2-t), akkor arra (az $(r_2,\Delta)$ állapotra) folytatjuk az elõbbi eljárást. Így elõbb-utóbb vagy elakadunk, mert a fal nem ad visszatérõ állapotot (csapda), vagy elõre lépünk végre valami q állapotba, ekkor $(q,\ldots)$ lesz a $(p_1,\Delta)$ állapothoz és az a karakterhez tartozó új állapot. Ha egyik eset se következik be |Q|+1 iteráción belül, akkor tutira volt ismétlõdõ állapot, azaz végtelen ciklusban vagyunk, azaz megint menjünk a csapdába. Ezzel láttuk, hogy az 1VA-ban az új állapot elsõ komponensét hogyan kell meghatározni. (b) Most lássuk, hogy hogyan kell a következõ falat kiszámolni! A $(p_1,\Delta)$ állapothoz és a karakterhez tartozó új állapot fala, a ${\Delta}'$ új fal a $\Delta$ és a a ismeretében kiszámolható. Azt kell megmondani minden q1 2VA állapot esetén, hogy ha q1 állapotban megyünk bele, azaz lépünk vissza, akkor visszatérünk-e és milyen 2VA állapotban. Ezt a következõképpen számolhatjuk ki. Ha a ${\Delta}'$-be q1-ben lépünk, akkor az azt jelenti, hogy q1 állapotban a-t olvasunk, hiszen a volt az utolsó karakter a fal elõtt. Ha a 2VA a (q1,a) párra (q2,j)-t ad, azaz elõre lép, akkor az új falban a q1 bemenõ állapothoz a q2 visszatérõ állapot tartozik. Ha 2VA a (q1,a) párra (q2,b)-t ad, azaz hátra lép, akkor meg az eddigi fal, a $\Delta$ mondja meg, hogy mi lesz. Ha $\Delta$ azt mondja, hogy nem tér vissza az automata, akkor a ${\Delta}'$ új falban a q1-re $\dagger$ lesz. Ha azt mondja a $\Delta$, hogy q3-ban tér vissza, akkor meg kell nézni, hogy a 2VA a (q3,a) párra mit tesz. Ha elõre lép q4-be, akkor a ${\Delta}'$-ben q4 lesz a visszatérõ állapot, ha visszafele, akkor megint konzultálunk a $\Delta$ fallal. Ez így megy max. |Q|+1 lépésig, mert ha addigra se akad el a 2VA, meg nem is mászik vissza teljesen, akkor biztosan lesz két ismétlõdõ állapot, azaz akkor végtelen ciklusban vagyunk, ekkor menjünk a csapdába. Így minden 1VA állapotra meg tudjuk határozni a következõ állapot mindkét komponensét. A kezdõállapot a $Q_0=(q_0,{\Delta}_0$ állapot lesz, ahol q0 a 2VA kezdõállapota, ${\Delta}_0$ meg az fal, a kezdõfal, ahol minden bemenõ állpothoz a $\dagger$ tartozik. (Ez azt fejezi ki, hogy függetlenül az állapottól, a szalag elején mindenki leesik a szakadékba.) Elfogadó állapotok azok lesznek az 1VA-ban, akiknek elsõ komponense elfogadó 2VA állapot. Ez azért van így, mert az elfogadáskor már nem számít a fal, az csak addig érdekes, amíg még tovább akarunk lépni.