NFA for binary strings containing 101
This NFA accepts binary strings that contain 101 as a substring. State q0 reads through any prefix and loops on both symbols. On a 1, it can also branch to q1 and treat that symbol as the start of a possible match. The path q1 to q2 to q3 then requires 0 followed by 1. Once q3 is reached, it loops on either symbol because the required substring has already been found. Nondeterminism matters when possible matches overlap: the q0 loop can continue scanning while another path tests a particular 1. This same pattern adapts naturally to searching for another fixed word or protocol marker.
Open it in the AI editor with a prompt pre-filled — keep what works, change what doesn't.
Scenario
Substring recognition
Key decisions
- Scanning loop: q0 can skip an arbitrary prefix.
- Nondeterministic start: a 1 can be ignored or treated as the first symbol of 101.
- Accepting loop: q3 permits any suffix after a completed match.
When to reuse this
Use this structure to recognize whether a short token occurs anywhere in a stream.
Frequently asked questions
Why is q3 an accepting state with loops?
Can overlapping matches be handled?
Does 1001 get accepted?
More automata theory examples
Try the diagram makers.
Tweak it with chat, export PNG/SVG, or fork it for your own use case.