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.