Converting Regular Expressions to NFA

Context: FIT2014_MOC · leg 1 of the Kleene’s Theorem cycle · Assignment 1 hand skill Problem it solves: given a regular expression, build an NFA recognising the same language.

Quick Revision

• 🎯 Trigger: a regex to turn into a machine ➔ start with one edge labelled the whole expression, then rewrite edges until every label is a single letter or $\epsilon$.
• ⚡ Key Constraint: the $R^{\ast }$ rule needs two $\epsilon$-transitions and a fresh middle state — putting the $R$-loop on the left or right node is wrong in general.

🔧 The procedure

Start with: a Start state and a Final state joined by a single edge labelled with the entire regular expression. Repeat: apply the rewrite rules below until every edge is labelled by a letter or $\epsilon$.

Edge label	Rewrite to
$\varnothing$	delete the edge (no transition at all)
$(R)$	a single edge labelled $R$ (brackets are only grouping)
$RS$	two edges in series through a new intermediate state: $\bullet \stackrel{R}{\to }\circ \stackrel{S}{\to }\bullet$
$R\cup S$	two parallel edges between the same pair, labelled $R$ and $S$
$R^{\ast }$	$\bullet \stackrel{\epsilon }{\to }\circ \stackrel{\epsilon }{\to }\bullet$ with a self-loop labelled $R$ on the new middle state

⭐ Why $R^{\ast }$ needs both $\epsilon$-transitions

stateDiagram-v2
    direction LR
    qin --> mid: ε
    mid --> mid: R
    mid --> qout: ε

• The danger ➔ if the $R$-loop were placed on the left node, any other edge arriving there (say $P$ or $Q$) could enter the loop, letting the machine match $P{R}^{\ast }Q$ — strings the original expression never described. Symmetrically for the right node with $S$, $T$.
• The fix ➔ the fresh middle state is reachable only via the two $\epsilon$-edges, so the loop is sealed off from the surrounding structure.
• Rule of thumb ➔ never attach a star-loop to a node that has other traffic.

📐 Worked example — $\mathtt{a}((\mathtt{ab}{)}^{\ast }\cup (\mathtt{ba})){\mathtt{b}}^{\ast }$

Stage	Edge labels present	Rule applied
0	$\mathtt{a}((\mathtt{ab}{)}^{\ast }\cup (\mathtt{ba})){\mathtt{b}}^{\ast }$	—
1	$\mathtt{a}$ · $(\mathtt{ab}{)}^{\ast }\cup (\mathtt{ba})$ · ${\mathtt{b}}^{\ast }$	concatenation (twice)
2	$\mathtt{a}$ · $(\mathtt{ab}{)}^{\ast }$ ∥ $\mathtt{ba}$ · ${\mathtt{b}}^{\ast }$	union ⟹ parallel edges
3	$\mathtt{a}$ · $(\mathtt{ab}{)}^{\ast }$ · $\mathtt{b},\mathtt{a}$ · ${\mathtt{b}}^{\ast }$	concatenation on $\mathtt{ba}$
4	star rules on $(\mathtt{ab}{)}^{\ast }$ and ${\mathtt{b}}^{\ast }$	each ⟹ $\epsilon$, middle state + loop
5	$\mathtt{a}$ · $\mathtt{b}$ · $\epsilon$ only	split the $\mathtt{ab}$ loop by concatenation

• Order is free ➔ any rule may be applied to any eligible edge; the resulting NFAs differ in shape but all recognise the same language.

✍️ Practice

Practice: Convert $\mathtt{a}(\mathtt{aa}\cup \mathtt{bb}{)}^{\ast }\mathtt{b}$ into an NFA with only letter/$\epsilon$ labels.

Reference solution

1. Concatenation ⟹ three edges in series: $\mathtt{a}$, then $(\mathtt{aa}\cup \mathtt{bb}{)}^{\ast }$, then $\mathtt{b}$.
2. Star on the middle edge ⟹ $\epsilon$ into a fresh state, a self-loop labelled $\mathtt{aa}\cup \mathtt{bb}$, $\epsilon$ out.
3. Union on the loop ⟹ two parallel loops labelled $\mathtt{aa}$ and $\mathtt{bb}$.
4. Concatenation on each ⟹ $\mathtt{a}\cdot \mathtt{a}$ and $\mathtt{b}\cdot \mathtt{b}$ through new middle states.

• Key move: apply star before union here, so the two $\epsilon$-edges seal the loop before it is split into branches.

⚠️ Common Mistakes

• 💡 $\varnothing$ deletes, it does not become a state ➔ an edge labelled $\varnothing$ is removable because no string matches it.
• 💡 Don’t skip the middle state for $R^{\ast }$ ➔ attaching the loop directly to an existing node lets neighbouring edges leak into the loop.
• 💡 Union means parallel, not sequential ➔ $R\cup S$ becomes two edges between the same pair of states; chaining them would encode $RS$.
• 💡 Stop only when every label is a letter or $\epsilon$ ➔ a leftover multi-letter label like $\mathtt{ab}$ means the conversion is unfinished.

🧠 Active Recall

Why does the $R^{\ast }$ rule introduce a new state and two $\epsilon$-transitions rather than looping on an existing node?

Answer

• Short answer: an existing node may have other incoming or outgoing edges ($P,Q$ on the left; $S,T$ on the right). A loop attached there could be entered from those edges, so the machine would accept strings like $P{R}^{\ast }Q$ that the original expression does not describe.
• Why: Isolation of the loop ➔ the fresh middle state is reachable only through the two $\epsilon$-edges, guaranteeing that repetitions of $R$ occur exactly where the star sits in the expression.