The request
“Draw an NFA over 0 and 1 that accepts strings containing 101: q0 loops on both symbols and can start a match on 1, followed by 0 to q2 and 1 to accepting q3, which loops on both symbols.”
Then tryChange the sought substring from 101 to 110.Remove the loops from q3 so the machine accepts only strings ending in 101.
What is in this drawing
Read the decisions behind it.
01Scanning loop
q0 can skip an arbitrary prefix.
02Nondeterministic start
a 1 can be ignored or treated as the first symbol of 101.
03Accepting loop
q3 permits any suffix after a completed match.
Use this structure to recognize whether a short token occurs anywhere in a stream.
More like this
Other examples in this family.
FAQ
Common questions
Why is q3 an accepting state with loops?
After finding 101, any remaining binary suffix still belongs to the language.
Can overlapping matches be handled?
Yes. Nondeterministic paths let the automaton test different starting positions at once.
Does 1001 get accepted?
No. It does not contain 101 as consecutive symbols.