NFA to DFA
1
Conversion from NFA to DFA
◼ Let, M = (Q, ∑, δ, q0, F) is an NFA
which accepts the language L(M). There
should be equivalent DFA denoted by
M' = (Q', ∑', q0', δ', F') such that L(M) =
L(M').
2
Conversion from NFA to DFA (cont’d...)
◼ Step 1: Initially Q' = ϕ
◼ Step 2: Add q0 of NFA to Q'. Then find the
transitions from this start state.
◼ Step 3: In Q', find the possible set of states for
each input symbol. If this set of states is not in Q',
then add it to Q'.
◼ Step 4: In DFA, the final state will be all the states
which contain F(final states of NFA)
3
Conversion from NFA to DFA (cont’d...)
◼ Example 1:
◼ Convert the given NFA to DFA.
4
Conversion from NFA to DFA (cont’d...)
◼ Solution: For the given transition diagram
we will first construct the transition table.
5
Conversion from NFA to DFA (cont’d...)
◼ Now we will obtain δ' transition for state ◼ Now we will obtain δ' transition
q0. on [q1, q2].
δ'([q0], 0) = [q0] δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0)
δ'([q0], 1) = [q1] = {q1, q2} ∪ {q2}
◼ The δ' transition for state q1 is obtained = [q1, q2]
as: ◼ δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2,
δ'([q1], 0) = [q1, q2] (new state generated) 1)
= {q1} ∪ {q1, q2}
δ'([q1], 1) = [q1] = {q1, q2}
◼ The δ' transition for state q2 is obtained = [q1, q2]
as:
δ'([q2], 0) = [q2]
δ'([q2], 1) = [q1, q2]
6
Conversion from NFA to DFA (cont’d...)
◼ The state [q1, q2] is the final state as well because
it contains a final state q2. The transition table for
the constructed DFA will be:
7
Conversion from NFA to DFA (cont’d...)
◼ The Transition diagram will be:
The state q2 can be eliminated because q2 is an
unreachable state. 8
NFA to DFA construction: Example
◼ L = {w | w ends in 01} 1 0
NFA: DFA: 0 1
0,1 [q0] [q0,q1] [q0,q2]
0
0 1 1
q0 q1 q2
δN 0 1
q0 {q0,q1} {q0}
q1 Ø {q2}
*q2 Ø Ø
9
A bad case where
#states(DFA)>>#states(NFA)
◼ L = {w | w is a binary string s.t., the kth symbol
from its end is a 1}
◼ NFA has k+1 states
◼ But an equivalent DFA needs to have at least 2 k
states
(Pigeon hole principle)
◼ m holes and >m pigeons
◼ => at least one hole has to contain two or more pigeons
10
Discussion Questions
Please refer
◼ TB_A2_NFA to DFA_Q.doc
◼ TB_A2_NFA to DFA_Ans.doc
11