Library

NFA · Regular

Finding “web” or “ebay”

Keyword search as an NFA: the start state loops on everything and, at each position, may guess that a keyword starts here. It accepts the texts that end in a keyword, so a search tool running it reports a hit each time it passes through an accepting state. x stands for any other letter.

12345678w, e, b, a, y…webebay
The machine as drawn — 8 states, 13 transitions.

The author’s examples, run

web → acceptebay → acceptxxweb → acceptwebebay → acceptwebx → rejectebxay → rejectwbe → rejecteba → reject