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. feladat Az s irány, azaz a semerre-se-lépés elhagyása nem gyengíti az automatát. 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. feladat Igaz-e, hogy mindig visszatér? Mi van ha nem tér vissza? Baj-e ez? Mi legyen ekkor? 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 megmpndja 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. feladat Mi van ha a (P,a) pár hatására a 2VA újra visszafele indul ismét? Meddig mehet ez a hátra-elõre lépegetés? Mi lesz az 1VA új állapota, mikor végre lelép arról a fránya a-ról, azaz milyen állapot tartozik majd az (R,a) párhoz az 1VA-ban? Harmadik ötlet Az aktuális visszatérési falat mi is nyilván tudjuk tartani magunknak, nem kell kérdezgetni senkit. 4.feladat Hányféle visszatérési fal lehetséges? 5. feladat Mi a kezdõfal? 6. feladat Ha a 2VA egy a-n áll most és a fej mögött a ${\Delta}$ v.f. van, hogyan határozzuk meg a következõ falat, azt ami mögé az a-t átlépve kerül az 1VA? 7.feladat Mit kell az 1VA állapotába belekódolni (két dolgot)? Mi lesz a kezdõállapot és mik lesznek a végállapotok? Hogy számolom az 1VA $\delta$ függvényét? 8. feladat Mi van, ha az eredeti 2VA nemdeterminisztikus volt? (Tipikus szigorlati kérdés...) A fentiek értelmében, hogyan néz ki ez a 2VA egyirányúsítva? $\delta(S,a)=(P,j)$ $\delta(S,b)=(Q,j)$ $\delta(P,a)=(P,j)$ $\delta(P,b)=(Q,j)$ $\delta(Q,a)=(S,b)$ $\delta(Q,b)=(S,j)$ Kezdõállapot az S, elfogadó állapotok az S és a P.