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آخر تحديث 24‏/9‏/2026

الطلب

“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.