Library

2DFA · Regular

Déjà vu, without guessing

The last letter appeared earlier — the language the two-way NFA decides by guessing which earlier letter matches. A deterministic two-way head does it with a second look instead: run to the end, read the last letter, go back to the start and search for it.

runlastrewArewBfindAfindBgotAgotBpastyes⊢, a, b⊣aba, b⊢a, b⊢abbaa, ba, ba, b⊣
The machine as drawn — 10 states, 23 transitions.

The author’s examples, run

aa → acceptabba → acceptaaa → acceptaaaaaaabba → acceptba → rejectbbba → rejectaab → rejectε → reject