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.

類型 狀態圖標準 OMG UML 2.5.1 §14 + Harel (1987) statechart引擎 schematex-state更新時間 2026/9/24

需求

“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.”

接著試試Add a dead state for a completed input that is rejected.Change the target suffix from ab to ba.

這張圖裡有什麼

看懂背後的決策。

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.

瀏覽所有狀態圖範本 →

常見問題

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.