A = (K,S,d,q₀,F), kde množina stavov K = (q₀,q₁,…,q_k), vstupná abeceda je S, d je prechodová funkcia, q₀ je počiatočný stav a F je množina akceptačných stavov.

Našou snahou je teda dokázať, že jazyk L' je tiež regulárny. A taktiež vieme, že nedeterministické konečné dvojsmerné automaty sú schopné rozpoznávať triedu regulárnych jazykov ( podobne, ako automaty DKA a NKA) (V skutočnosti príslušná veta znie takto: " Trieda jazykov akceptovaná dvojsmerným deterministickým konečným automatom je R". My síce teraz pracujeme s nedeterministickým kon. automatom, ale predošlé tvrdenie sa dá zovšeobecniť pre všetky dvojsmerné kon. automaty.). Skonštruujme teraz nedeterministický dvojsmerný automat tak, aby prvé dve tretiny vstupného slova rozpoznával na základe automatu A, a chýbajúcu zvyšnú tretinu by nedeterministicky uhádol.

A' = (K',S,D ,q₀,F'), kde
K' = K Č {q_a' (" q_a Î K)} Č {q_aL' (" q_a Î K)} Č {q_FINAL} (q_a' a q_aL' sú tzv. cúvajúce stavy)
S' = S (lebo pracujeme nad tou istou abecedou)
q₀ =q₀
F' = {q_FINAL}

D(q_a,x) = {(q_b,1)} Ű d(q_a,x) = q_b & xÎ S'
D(q_a,$) = {(q_a',-1)}
D(q_a',x) = {(q_aL',-1)} xÎ S'
D(q_aL',x) = {(q_b',-1)} Ű d(q_a,y) = q_b "yÎ S' & xÎ S'
D(q_a',¢) = {(q_FINAL,1)} ak q_aÎF
D(q_FINAL,x) = {(q_FINAL,1)} "xÎ S'

Automat pracuje nasledovne:

1. Najprv smerom zľava doprava 'emuluje' činnosť automatu A. Na to slúži časť delta-funkcie: D(q_a,x) = {(q_b,1)} Ű d(q_a,x) = q_b & xÎ S'
   
2. Pohybuje doprava až kým nepríde na vstup symbol $. D(q_a,$) = {(q_a',-1)}. Teraz prejde do špeciálneho stavu q_a'. Tieto stavy označené s čiarou zabezpečia pohyb na vstupnej páske vlavo.
   
3. Automat na spätnej ceste nedeterministicky určuje postupnosť stavov tak, aby dĺžka suffixu bola polovica načítaného slova. Pri tom ’ozajstný vstup’ (okrem znakov ¢,$ samozrejme) je ignorovaný. To zabezpečia prípady: D(q_a',x) = {(q_aL',-1)} xÎ S' a D(q_aL',x) = {(q_b',-1)} Ű d(q_a,y) = q_b "yÎ S' & xÎ S'
   
4. Ak sa automat rozhodoval správne - v okamihu, keď čitacia hlava stojí na začiatku vstupu - mal by byť v akceptačnom stave. D(q_a',¢) = {(q_FINAL,1)} ak q_aÎF
   
5. Teoreticky už v tomto momente by sme mohli akceptovať dané slovo, ale podľa formálnej definície dvojsmerných automatov čitacia hlava by mala byť na konci vstupného slova. A teda D(q_FINAL,x) = {(q_FINAL,1)} "xÎ S'