NFA to DFA conversion in Compiler Design - Step-by-Step Execution

Concept Flow - NFA to DFA conversion

Start with NFA

↓

Identify NFA states and transitions

↓

Create initial DFA state as epsilon-closure of NFA start

↓

For each DFA state, for each input symbol

↓

Find reachable NFA states (move + epsilon-closure)

↓

Add new DFA state if not already present

↓

Repeat until no new DFA states

↓

Mark DFA final states if contain NFA final states

↓

Result: DFA equivalent to NFA

The flow starts from the NFA, builds DFA states by grouping NFA states reachable via inputs, and repeats until all DFA states are found.

Execution Sample

Compiler Design

NFA states: {q0, q1, q2}
Input: {a, b}
Start: q0
Final: q2
Transitions:
q0 -a-> q0,q1
q1 -b-> q2

This NFA has three states with transitions on 'a' and 'b'. We convert it step-by-step into a DFA.

Analysis Table

Step	DFA State (NFA states)	Input Symbol	Move Result	Epsilon-Closure	New DFA State Added?
1	{q0}	a	{q0, q1}	{q0, q1}	Yes (DFA state A)
2	{q0}	b	{}	{}	No
3	{q0, q1}	a	{q0, q1}	{q0, q1}	No
4	{q0, q1}	b	{q2}	{q2}	Yes (DFA state B)
5	{q2}	a	{}	{}	No
6	{q2}	b	{}	{}	No
7	No new DFA states found, conversion complete

💡 All reachable DFA states created; no new states to add.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 4	Final
DFA States	{}	{q0}, {q0,q1} (A)	{q0}, {q0,q1} (A)	{q0}, {q0,q1} (A), {q2} (B)	{q0}, {q0,q1}, {q2}
Worklist	[{q0}]	[{q0,q1}]	[{q0,q1}]	[{q2}]	[]

Key Insights - 3 Insights

Why do we take epsilon-closure after the move operation?

Because NFA can move through epsilon transitions without input, epsilon-closure finds all reachable states after a move. See execution_table rows 1 and 4 where epsilon-closure expands the move result.

How do we know when to stop adding new DFA states?

When no new sets of NFA states appear after processing all inputs for all DFA states. Execution_table row 7 shows this stopping condition.

Why is a DFA state represented as a set of NFA states?

Because each DFA state corresponds to a group of NFA states reachable together, capturing all possible NFA configurations at once. This is shown in variable_tracker where DFA states are sets like {q0,q1}.

Visual Quiz - 3 Questions

According to the execution_table, what is the epsilon-closure of the move from {q0} on input 'a'?

A {}

B {q0, q1}

C {q0}

D {q2}

💡 Hint

Check execution_table row 1 under 'Epsilon-Closure' column.

At which step does the DFA state {q2} get added?

A Step 4

B Step 2

C Step 5

D Step 6

💡 Hint

Look at execution_table row 4 under 'New DFA State Added?' column.

If the NFA had an epsilon transition from q1 to q2, how would the epsilon-closure of {q0, q1} change?

A It would remain {q0, q1}

B It would exclude q1

C It would include q2

D It would become empty

💡 Hint

Epsilon-closure includes all states reachable via epsilon transitions; see variable_tracker for how sets expand.

Concept Snapshot

NFA to DFA conversion:
- Start with NFA start state's epsilon-closure as DFA start
- For each DFA state and input, find reachable NFA states (move + epsilon-closure)
- Add new DFA states for unseen sets
- Repeat until no new states
- DFA states represent sets of NFA states
- Final DFA accepts if any NFA final state is in the set

Full Transcript

This visual execution traces converting a Non-deterministic Finite Automaton (NFA) to a Deterministic Finite Automaton (DFA). We start with the NFA's start state and find its epsilon-closure to form the initial DFA state. For each DFA state, we check each input symbol to find which NFA states are reachable by moving on that input, then take their epsilon-closure. If this set of states is new, we add it as a new DFA state. We repeat this process until no new DFA states appear. The DFA states are sets of NFA states, capturing all possible NFA configurations deterministically. The process ends when all reachable states are processed, resulting in a DFA equivalent to the original NFA.