Lecture No. 08

Dated: 17-03-2025

NFA¹ → DFA² Construction

The algorithm is called the subset construction. The transition table³ of NFA¹ contains multiple states meanwhile the DFA² contains single states.
Therefore, each state in DFA² corresponds to multiple states in NFA.¹

Following are the operations

• \(\epsilon-closure(T)\) for set⁴ of NFA¹ states reachable from some NFA¹ state \(s\) in \(T\) on \(\epsilon\) transitions alone.
• \(move(T, a)\) for set⁴ of NFA¹ states to which there is a transition on input \(a\) from some state \(s\) in NFA¹ in \(T\).

Subset Construction

Algorithm

Input:

• NFA¹ \(N\)
• states set⁴ \(S\)
• Alphabet \(\Sigma\)
• State state \(s_0\)
• Final state \(F\)

Output:

• DFA¹ \(D\)
• states set⁴ \(S^\prime\)
• Alphabet \(\Sigma\)
• State state \(s_0^\prime = \epsilon-closure(s_0)\)
• Final state \(F^\prime\)
• Transition table³ \(S^\prime \times \Sigma ? S^\prime\)

---

\(S^\prime = \{s_0^\prime\}\) (unmarked)
while(there is some unmarked state in \(T\) in \(S^\prime\))
mark state \(T\)
for all \(a\) in \(\Sigma\) do
\(U = \epsilon-enclosure(move(T, a))\)
if \(U\) not already in \(S^\prime\)
add \(U\) as unmarked state to \(S^\prime Dtran(T, a) = U\)
end if
end for
end while
\(F^\prime\):
for each DFA¹ state \(S\)
if \(S\) contains an NFA¹ final state
mark \(S\) as DFA¹ final state
end algorithm

Example

NFA¹ for \((a | b)^*abb\) with \(\Sigma = \{a, b\}\).

The start state of DFA¹ is \(\epsilon-closure(0)\) which is \(A = \{0, 1, 2, 4, 7\}\). These are the states which are reachable from \(0\) through \(\epsilon\) transitions.
According to algorithm, mark \(A\) and compute \(\epsilon-enclosure(move(A, a))\).
\(move(A, a)\) is the set⁴ of state in NFA¹ that have transitions on input \(a\) from members of \(A\).

\[2 \to 3\]

\[7 \to 8\]

\[\epsilon-enclosure(move(A, a)) = \epsilon-enclosure(\{3, 8\}) = \{1, 2, 3, 4, 6, 7, 8\}\]

Let

\[B = \{1, 2, 3, 4, 6, 7, 8\}\]

Thus

\[Dtran[A, a] = B\]

For input \(b\),

\[4 \to 5\]

\[C = \epsilon-closure(\{5\}) = \{1, 2, 4, 5, 6, 7\}\]

Let

\[C = \{1, 2, 4, 5, 6, 7\}\]

Thus,

\[Dtran[A, b] = C\]

We continue this process with unmarked sets \(B\) and \(C\) until all sets⁴ of DFA² are marked.

1. \(A=\{0,1,2,4,7\}\)
2. \(B=\{1,2,3,4,6,7,8\}\)
3. \(C=\{1,2,4,5,6,7\}\)
4. \(D=\{1,2,4,5,6,7,9\}\)
5. \(E=\{1,2,4,5,6,7,10\}\)

\(A\) is starting state as it contains \(0\) and \(E\) is the accepting state because it contains \(10\).

State	Input symbol
	a	b
A	B	C
B	B	D
C	B	C
D	B	E
E	B	C

References

---

1. Read more about non deterministic finite automaton. ↩↩↩↩↩↩↩↩↩↩↩↩↩↩↩

2. Read more about finite automaton. ↩↩↩↩

3. Read more about transition table. ↩↩

4. Read more about sets. ↩↩↩↩↩↩