NFA with Epsilon Transitions for A or B

NFA with epsilon transitions for a or b

This epsilon-NFA accepts the language described by the regular expression a|b. It begins at q0 and takes one of two epsilon transitions, which change state without consuming an input symbol. The upper branch reaches q1 and accepts an a; the lower branch reaches q2 and accepts a b. Both branches end at qf, the accepting state. The drawing is a small version of the union rule used in Thompson construction: introduce a new start state, split by epsilon to the alternatives, then join successful alternatives at a shared final state. Because epsilon moves consume nothing, the choice of branch is made before the machine reads the only input symbol.

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

需求

“Draw an epsilon-NFA for the regular expression a|b: start at q0, branch by epsilon to q1 and q2, read a from q1 or b from q2, then reach accepting qf.”

接著試試Add a third epsilon branch that accepts c.Replace the union with a concatenation that accepts ab.

這張圖裡有什麼

看懂背後的決策。

01Epsilon split

q0 reaches either branch without consuming input.

02Separate symbols

each branch consumes exactly one alternative.

03Shared accepting state

both successful paths merge at qf.

Use an epsilon split when translating a regular-expression union into an NFA.

瀏覽所有狀態圖範本 →

常見問題

What does ε mean on an arrow?

It means the automaton changes state without reading an input symbol.

Does this NFA accept the empty string?

No. Each path to qf must still consume either a or b.

Why do both branches end at qf?

A shared accepting state expresses that either alternative is a successful match.