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.