What if the machine could guess?
Design a DFA for strings that contain aba somewhere. It's doable but fiddly: when a match fails halfway, you must work out how much of it can be reused. Now imagine a machine allowed to guess: on any a, it may guess "the aba starts here" and check the next two symbols. If any guess works out, the string is accepted. That machine is tiny and obviously right.
That's an NFA, a nondeterministic finite automaton. It sounds like magic, but there's no guessing in practice: we simulate it by following every possible path at once, keeping a set of current states. Michael Rabin and Dana Scott introduced the idea in 1959 and won the Turing Award for it.
Sets of states
In an NFA, delta[state][symbol] is a list of states — possibly empty, possibly several. Simulation keeps the set of all states the machine could be in. For each symbol, the new set is everything reachable from any current state on that symbol. Paths with no move simply die. At the end, accept if any state in the set is an accept state.
const CONTAINS_ABA = {
start: "q0",
accept: ["q3"],
delta: {
q0: { a: ["q0", "q1"], b: ["q0"] },
q1: { b: ["q2"] },
q2: { a: ["q3"] },
q3: { a: ["q3"], b: ["q3"] },
},
};Rejection in an NFA means every path failed. One accepting path is enough.