Library

2NFA · Regular

Déjà vu: the last letter is a rerun

@thethinkmachine·version 1·CC BY 4.0·added 28 Sept 2026

Accepts strings whose final letter occurred earlier too. The 2NFA guesses the earlier occurrence, races to the end marker, and steps back to confirm the match.

Open in AutomataStudio
More
Open in the desktop app Download the .automaton file Source on GitHub
scansawArunAcheckAsawBrunBcheckBacc⊢, a, baba, ba, b⊣aa, ba, b⊣b
The machine as drawn — 8 states, 17 transitions.

The author’s examples, run

aba → acceptabb → acceptabab → acceptab → rejectba → rejecta → reject