Kétirányú automata: ugyanolyan, mint az eddig megszokott véges automata, annyi különbséggel, hogy a átmeneti függvény egy állapotból és egy karakterből álló párhoz egy új állapotot és egy irányt ( {  l,r,s  }) rendel, az irány szerint lép az automata balra, jobbra vagy semerre.

Lehet nem determinisztikus is, most azonban nézzünk egyenlőre csak determinisztikusakat. Rövitítés: 2VA.
  
Picard kapitány sejtése: A kétirányú automaták sem erősebbek mint az egyirányúak, a 2VA-k 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.
  
Picard kapitány első ötlete: 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?
  
Picard kapitány második ötlete: Ne várjuk meg amíg visszatér (pláne, mert lehet, hogy nem is tér vissza), hanem kérdezzük meg Data-t, hogy visszatér-e majd és ha igen, akkor milyen állapotban? Data baromi okos, ezt meg tudja mondani. Ha pl. a 2VA egy (R,a) párra a (Q,l) párral válaszol, tehát elindul visszafelé, akkor Picard megkérdezi Data-t, hogy a Q-hoz milyen visszatérő állapot tartozik (mondjuk ez P) és ekkor a szimulációt a P állapotból folytatja, azaz a megnézi, hogy a 2VA mit tesz a (P,a) párra?
  
3. feladat Mért a (P,a) párt kell nézni? Mi van ha a (P,a) pár hatására a 2VA újra visszafele indul? Meddig mehet ez a 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?
  
4. feladat Mi az a két információ, amire Picard-nak szüksége van, hogy szimulálni tudjon?

Data-t ideiglenesen másik csillaghajóra helyezik, a kapitánynak magának kell boldogulnia. Rájön, hogy nincs is szüksége (a szimulációhoz) Data-ra, az aktuális visszatérési falat maga is nyilván tudja tartani.

  
5.feladat Hányféle visszatérési fal lehetséges?
  
6. feladat Ha a 2VA egy a-n áll most és a fej mögött a v.f. van, hogyan határozza meg a kapitány a következő falat, azt ami mögé az a-t átlépve kerül?
  
7. feladat Mi a kezdőfal?
  
8.feladat Mit kell az 1VA állapotába belekódolni? Mi lesz a kezdőállapot és mik lesznek a végállapotok? Mi lesz az 1VA függvénye? Hogy számolom ki?
  
9.feladat Végiggondolni az egész szimulációt!!!!
  
10. feladat És ha az eredeti 2VA nemdeterminisztikus volt?

  
A fentiek értelmében, hogyan néz ki ez a 2VA egyirányúsítva?
(A,a) = (A,r)
(A,b) = (B,r)
(B,a) = (A,r)
(B,b) = (B,l)

Kezdőállapot az A, elfogadó állapotok az A és a B.