NFA for strings ending in ab
This NFA recognizes every string over the alphabet a and b whose final two symbols are ab. State q0 scans any prefix. When it reads an a, it may either stay in q0 or guess that this a begins the required final suffix and move to q1. If the next symbol is b, q1 reaches accepting state q2. The parallel a transitions from q0 are the nondeterministic part: the machine can keep scanning and test a possible suffix start at the same time. A string is accepted if at least one path ends in q2 when the input finishes. This is a useful first example because its state diagram makes the difference between nondeterministic and deterministic recognition visible without adding unnecessary states.
Open it in the AI editor with a prompt pre-filled — keep what works, change what doesn't.
Scenario
Recognizing a suffix
Key decisions
- Nondeterministic choice: q0 keeps scanning while also guessing that an a starts the final suffix.
- Accepting state: q2 is reached only after the guessed a is followed by b.
- Compact layout: three states isolate the essential transition logic.
When to reuse this
Use this pattern when an automaton needs to recognize a fixed ending without remembering the whole prefix.
Frequently asked questions
Why does q0 have two transitions on a?
Which strings are accepted?
Is q2 accepting only at end of input?
More automata theory examples
Try the diagram makers.
Tweak it with chat, export PNG/SVG, or fork it for your own use case.