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.