Library

NFA · Regular

The last letter has appeared before

Guess which earlier letter will turn out to match the last one, remember only that letter, and accept if the word ends on it. The one-way version of the two-way “déjà vu” machine: here the guess does the work the head’s second look does there.

startgotAgotBgotCmatcha, b, cabca, b, caa, b, cba, b, cc
The machine as drawn — 5 states, 18 transitions.Every word up to length 5, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

aa → acceptabacbbc → acceptacca → acceptabbcaababcaccb → acceptba → rejectabaabbc → rejectbcca → rejectε → reject