NFA for Strings Starting with A or BB

NFA for strings starting with a or bb

This epsilon-NFA illustrates a language with alternative prefixes. It reads the first symbol at q0. An a moves to qa, while a b moves to q1, which needs a second b to reach qb. The two successful branches then merge into qf by epsilon, where the machine can consume any remaining symbols. The epsilon transitions mean the required prefix itself is enough for acceptance; no extra input is needed before qf. The drawing shows that acceptance depends on the beginning of the input rather than its end. Prefix languages are common in token recognition, command parsing and protocol dispatch, where the first few symbols choose a valid form.

유형 상태 다이어그램표준 OMG UML 2.5.1 §14 + Harel (1987) statechart엔진 schematex-state업데이트됨 2026. 9. 24.

요청 내용

“Draw an epsilon-NFA over a and b that accepts strings beginning with a or bb: q0 goes to qa on a or q1 on b, q1 goes to qb on b, and either successful branch reaches accepting qf by epsilon, which loops on a and b.”

그렇다면Replace the epsilon transitions to qf with transitions that consume c.Add a branch that accepts strings starting with baa.

이 도면에 담긴 내용

그 이면의 의사결정을 읽어 보세요.

01Branching prefix

q0 separates the a and bb alternatives.

02Successful merge

qa and qb lead to one accepting continuation.

03Suffix loop

qf accepts arbitrary remaining input after a valid prefix.

Use a branch-and-merge automaton for a language defined by several allowed starting patterns.

모든 상태 다이어그램 템플릿 보기 →

자주 묻는 질문

What prefixes does the machine recognize?

It recognizes inputs whose beginning is a or bb, followed by a binary suffix.

Why is there a separate q1 state?

It records that the first b has been read and a second b is required.

Can the branches share one final state?

Yes. Both branches express valid prefixes, so they can merge before consuming the rest of the input.