DFA · Regular
Finding the EcoRI site GAATTC in DNA
The restriction enzyme EcoRI cuts DNA at GAATTC. A DFA finds it in one pass: each state is how much of the site has just been matched, and a mismatch falls back to the longest part that still fits — the Knuth–Morris–Pratt idea.
The author’s examples, run
GAATTC → acceptACGTGAATTCTA → acceptGAATTCTA → acceptACGTGAATTCTATA → acceptAAATTC → rejectACGTAAATTCTA → rejectAAATTCTA → rejectACGTAAATTCTATA → reject