NFA for Strings Ending in AB

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.

Tipo Diagrama de estadosNorma OMG UML 2.5.1 §14 + Harel (1987) statechartMecanismo schematex-stateAtualizado 24/09/2026

A solicitação

“Draw an NFA over a and b that accepts exactly the strings ending in ab: q0 loops on a and b, q0 can move to q1 on a, and q1 moves to accepting q2 on b.”

Depois, tenteAdd a dead state for a completed input that is rejected.Change the target suffix from ab to ba.

O que há neste desenho

Entenda as decisões por trás dele.

01Nondeterministic choice

q0 keeps scanning while also guessing that an a starts the final suffix.

02Accepting state

q2 is reached only after the guessed a is followed by b.

03Compact layout

three states isolate the essential transition logic.

Use this pattern when an automaton needs to recognize a fixed ending without remembering the whole prefix.

Ver todos os modelos de diagrama de estados →

Perguntas frequentes

Dúvidas comuns

Why does q0 have two transitions on a?

One transition continues scanning the prefix and the other guesses that this a starts the final ab suffix.

Which strings are accepted?

Examples include ab, aab and bab. A string such as aba is not accepted because it does not end in ab.

Is q2 accepting only at end of input?

Yes. Acceptance requires a path to finish in q2 after the entire input has been read.