DHARM194 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
I. Since, QD ⊆ P (Q) or power set of Q where Q = {q 0 , q 1 , q 2 , q 3 }, hence
P(Q) = [Φ, {q 0 }, {q 1 },{q 2 },{q 3 },{q 0 , q 1 },{q 0 , q 2 },{q 0 , q 3 },{q 1 , q 2 }, {q 1 , q 3 },{q 2 , q 3 },
{q 0 , q 1 , q 2 }, {q 0 , q 2 , q 3 }, {q 1 , q 2 , q 3 }, {q 0 , q 1 , q 3 },{q 0 , q 1 , q 2 , q 3 }]
From the set of P(Q) we will select the states for QD that are used for the construction of
an equivalent DFA. It is possible that some of the states in the P(Q) might not be accessible
from starting state of DFA directly or indirectly, so leave those states. Remember that club of
the states shown inside the braces represents a single state. Transition from this club of state
over input symbols must be same the transitions from each states in the club over same input
symbol. For example, state {q 0 , q 1 , q 2 , q 3 } is a single state and the transitions from this state
satisfies all transitions of each state q 0 , q 1 , q 2 , q 3 over Σ = {0,1}.
II. Both automatons start from same state, hence start state of DFA, i.e., {q 0 } = {q 0 } of
NFA.
III. From NFA we know the final set of states is FN. Certainly, the final set of states of
DFA is FD (⊆ QD) that should contains at least one state in common with FN i.e.,
FD ∩ FN ≠ Φ
III. Now compute transition functions δD for DFA over input alphabet Σ for set of states
QD.
· Transition from the state Φ that is truly no state, over symbol 0 and 1 are nothing, so
return state will be Φ.
· Next state in the set QD is {q 0 }, so
δD(q 0 , 0) = {q 0 , q 1 } and δD(q 0 , 1) = {q 0 };
· Transition from states {q 1 }, {q 2 }, {q 3 } over symbol 0 and 1 are same as shown in TT i.e.,
δD(q 1 , 0) = Φ and δD(q 1 , 1) = {q 2 };
δD(q 2 , 0) = {q 3 } and δD(q 2 , 1) = Φ
δD(q 3 , 0) = {q 3 } and δD(q 0 , 1) = {q 3 };
· Transitions from the state {q 0 , q 1 } is obtain as,
δD({q 0 , q 1 }, 0) = δN(q 0 , 0) ∪ δN(q 1 , 0)
= {q 0 , q 1 } ∪ Φ = {q 0 , q 1 };
and δD({q 0 , q 1 }, 1) = δN(q 0 , 1) ∪ δN(q 1 , 1)
= {q 0 } ∪ {q 2 } = {q 0 , q 2 };
· Similarly, transitions from all other states of the set P(Q) over input alphabets is
determine.
· For the final state {q 0 , q 1 , q 2 , q 3 } δD will be,
δD({q 0 , q 1 , q 2 , q 3 }, 0) = δN(q 0 , 0) ∪ δN(q 1 , 0) ∪ δN(q 2 , 0) ∪ δN(q 3 , 0)
= {q 0 , q 1 } ∪ Φ ∪ {q 3 } ∪ {q 3 }
= {q 0 , q 1 , q 3 };
and δD({q 0 , q 1 , q 2 , q 3 }, 1) = δN(q 0 , 1) ∪ δN(q 1 , 1) ∪ δN(q 2 , 1) ∪ δN(q 3 , 1)
= {q 0 } ∪ {q 2 } ∪ Φ ∪ {q 3 }
= {q 0 , q 2 , q 3 };