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.