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.
The author’s examples, run
aa → acceptabba → acceptaaa → acceptaaaaaaabba → acceptba → rejectbbba → rejectaab → rejectε → reject