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?
Tweak it with chat, export PNG/SVG, or fork it for your own use case.