Chapter Two

Lecture -3

DFA State Minimization and λ-removal

 State Minimization
• Larger number of states in FA require higher memory and computing power.

• An NFA of n states result to maximum number of states in an equivalent DFA, therefore

design of DFA is crucial

• Minimization of a DFA refers to detecting those states whose absence does not affect the
language acceptability of DFA.

• A reduced Automata consumes lesser memory, and complexity of implementation is reduced.

• This results to faster execution time, easier to analyze.

• STGs may contain redundant states, i.e. states whose function can be accomplished by other
states.

• State minimization is the transformation of a given machine into an equivalent machine with
 Key terms
• Unreachable states: If there does not exist any q′, such that δ∗(q0,w) = q′, then q′ is unreachable/inaccessible state.

• Dead state: All those non-final states which transit to itself for all input symbols in ∑ are called as dead states.
• ∀a, a ∈ Σ, q is dead state if δ(q,a) = q and q ∈ Q - F.

• Reachability: FA M is accessible if ∃w, w ∈ Σ∗, and (q0,w) ⊢∗ (q,ε) for all q ∈ Q. ⊢∗ is called reachability relation.

• Inaccessible State: All those states which can never be reached from the initial state are called as inaccessible states.

• Indistinguishable states: Two states are indistinguishable if their behavior are indistinguishable with respect to each other.

• For example, p,q are indistinguishable if

• δ∗(p,w) = δ∗(q,w) = r ∈ Q for all w ∈ Σ∗.

• k-equivalence: p,q are k-equivalence if:

• δ∗(q,w) ∈ F ⇔ δ∗(p,w) ∈ F, for all w ∈ Σ∗ and |w| ≤ k;

• written as p ∼k q. If they are equivalent for all k,

• then p ∼ k. The p ∼ q and p ∼k q are equivalent relations.

 Minimization of DFA Using Equivalence Theorem
• Step-01: Eliminate all the dead states and inaccessible states from the given DFA (if any).

• Step-02: Draw a state transition table for the given DFA. Transition table shows the transition of all states on all input symbols in Σ.

• Step-03: Now, start applying equivalence theorem.

• Take a counter variable k and initialize it with value 0.

• Divide Q (set of states) into two sets such that one set contains all the non-final states and other set contains all the final states. This

partition is called P0.

• Step-04: Increment k by 1.

• Find Pk by partitioning the different sets of Pk-1 .

• In each set of Pk-1 , consider all the possible pair of states within each set and if the two states are distinguishable, partition the set into

different sets in Pk.

• Step-05: Repeat step-04 until no change in partition occurs. In other words, when you find Pk = Pk-1, stop

• Step-06: All those states which belong to the same set are equivalent. The equivalent states are merged to form a single state in the minimal

DFA.
 Cont’d
• Example: Consider the following DFA shown in figure
0 1
q0 {q3} {q1}
q1 {q2} {q5}
q2 {q2} {q5}
q3 {q0} {q4}
q4 {q2} {q5}
q5 {q5} {q5}

• Step 1. P0 will have two sets of states. One set will contain q1, q2, q4 which are final
states of DFA and another set will contain remaining states.
• So P0 = { { q1, q2, q4 }, { q0,q3, q5 } }.
• Step 2. To calculate P1, we will check whether sets of partition P0 can be partitioned or
not:
 Cont’d
• i) For set { q1, q2, q4 }
• δ ( q1, 0 ) = δ ( q2, 0 ) = q2 and δ ( q1, 1 ) = δ ( q2, 1 ) = q5, So q1 and q2 are not
distinguishable.
• Since, q1 and q2 are not distinguishable and q1 and q4 are also not distinguishable, So q2
and q4 are not distinguishable. So, { q1, q2, q4 } set will not be partitioned in P1.
• ii) For set { q0, q3, q5 } :
• δ ( q0, 0 ) = q3 and δ ( q3, 0 ) = q0, δ ( q0, 1) = q1 and δ( q3, 1 ) = q4
• Moves of q0 and q3 on input symbol 0 are q3 and q0 respectively which are in same set in
partition P0.
• Similarly, Moves of q0 and q3 on input symbol 1 are q1 and q4 respectively which are in
same set in partition P0. So, q0 and q3 are not distinguishable.
• δ ( q0, 0 ) = q3 and δ ( q5, 0 ) = q5 and δ ( q0, 1 ) = q1 and δ ( q5, 1 ) = q5
• Moves of q0 and q5 on input symbol 1 are q1 and q5 respectively which are in different
set in partition P0. So, q0 and q5 are distinguishable. So, set { q0, q3, q5 } will be
partitioned into { q0, q3 } and { q5 }.
• So, P1 = { { q1, q2, q4 }, { q0, q3}, { q5 } }
• To calculate P2, we will check whether sets of partition P1 can be partitioned or not:
 Cont’d
• iii) For set { q1, q2, q4 } :
• δ ( q1, 0 ) = δ ( q2, 0 ) = q2 and δ ( q1, 1 ) = δ ( q2, 1 ) = q5, So q1 and q2 are not
distinguishable.
• Similarly, δ ( q1, 0 ) = δ ( q4, 0 ) = q2 and δ ( q1, 1 ) = δ ( q4, 1 ) = q5, So q1 and q4 are
not distinguishable.
• Since, q1 and q2 are not distinguishable and q1 and q4 are also not distinguishable, So q2
and q4 are not distinguishable. So, { q1, q2, q4 } set will not be partitioned in P2.
• iv)For set { q0, q3 } :
• δ ( q0, 0 ) = q3 and δ ( q3, 0 ) = q0; δ ( q0, 1 ) = q1 and δ ( q3, 1 ) = q4
• Moves of q0 and q3 on input symbol 0 are q3 and q0 respectively which are in same set
in partition P1.
• Similarly, Moves of q0 and q3 on input symbol 1 are q1 and q4 which are in same set in
partition P1. So, q0 and q3 are not distinguishable.
• v) For set { q5 }: Since we have only one state in this set, it can’t be further partitioned. So,
• P2 = { { q1, q2, q4 }, { q0, q3 }, { q5 } }
 Cont’d
• Corresponding to DFA of figure 1 is shown in figure 2 as:
 Exercise
• Minimize the following DFAs

A B
 DFA Minimization using Myhill-Nerode Theorem

• Algorithm

• Input – DFA

• Output - Minimized DFA

• Step 1 - Draw a table for all pairs of states (,) not necessarily connected directly [All are
unmarked initially]
• Step 2 - Consider every state pair (,) in the DFA where ∈ F and ∉ F or vice versa and mark
them. [Here F is the set of final states]
• Step 3 - Repeat this step until we cannot mark anymore states -
If there is an unmarked pair (,), mark it if the pair {δ (, A), δ (, A)} is marked for some input
alphabet.
• Step 4 - Combine all the unmarked pair (,) and make them a single state in the reduced DFA .
 DFA Minimization using Myphill-Nerode Theorem
• Example: Let us use above algorithm to minimize the DFA shown below.

Step 1 - We draw a table for all pair of states.

a b c d e f
a X X X X X
b X X X X
c ٧ ٧ X X X
d ٧ ٧ X X
e ٧ ٧ X
f ٧ ٧ ٧
 Cont’d
We will try to mark the state pairs, with green colored check mark, transitively. If we
• Step 3 -
input 1 to state ‘a’ and ‘f’, it will go to state ‘c’ and ‘f’ respectively. c, f is already marked,
hence we will mark pair a, f. Now, we input 1 to state ‘b’ and ‘f’; it will go to state ‘d’ and ‘f’
respectively. d, f is already marked, hence we will mark pair b, f
a b c d e f
a X X X X X • After step 3, we have got state combinations
b X X X X {a, b} {c, d} {c, e} {d, e} that are
c ٧ ٧ X X X unmarked.
d ٧ ٧ X X • We can recombine {c, d} {c, e} {d, e} into
e ٧ ٧ X {c, d, e}
f ٧ ٧ ٧ ٧ ٧ • Hence we got two combined states as - {a,
b} and {c, d, e}.
• So the final minimized DFA will contain
three states {f}, {a, b} and {c, d, e}
 Conversion of Epsilon-NFA to NFA
• Non-deterministic Finite Automata (NFA) is a finite automata having zero, one or more
than one moves from a given state on a given input symbol. 
• Epsilon NFA is the NFA which contains epsilon move(s)/Null move(s).
• To remove the epsilon move/Null move from epsilon-NFA and to convert it into NFA, we
follow the steps mentioned below.
• ε -NFAs add a convenient feature but (in a sense) they bring
• us nothing new: they do not extend the class of languages
• that can be represented. Both NFAs and ε-NFAs recognize
• exactly the same languages.
 Cont’d
• To remove the epsilon move/Null move from epsilon-NFA and to convert it into NFA, we follow the steps
mentioned below.

• Step-1: Considering the epsilon move from state q0 to state q2. Consider the state q0 as vertex v1 and state q2 as
vertex v2.

• Step-2: Now find all the moves that starts from vertex v2 (i.e. state q2).

• Step-3: See that if the vertex v1 is a start state or not. If vertex v1 is a start state, then we will also make vertex v2
as a start state. If vertex v1 is not a start state, then there will not be any change.

• Step-4: See that if the vertex v2 is a final state or not. If vertex v2 is a final state, then we will also make vertex
v1 as a final state. If vertex v2 is not a final state, then there will not be any change.

• Repeat the steps(from step 1 to step 4) until all the epsilon moves are removed from the NFA.
 Cont’d
• Example: Convert epsilon-NFA to NFA.
• Consider the example having states q0, q1, q2, q3, and q4.
States/Input Input 0 Input 1 Input epsilon

q0 – q1 q2

q1 – q0 –

q2 q3 q4 –

q3 q2 – –

q4 q2 – –

Step-1:
Considering the epsilon move from state q0 to state q2. Consider the state q0 as vertex v1 and state q2 as
vertex v2.
 Cont’d
• Step-2: Now find all the moves that starts from vertex v2 (i.e. state q2).
• After finding the moves, duplicate all the moves that start from vertex v2 (i.e state q2) with
the same input to start from vertex v1 (i.e. state q0) and remove the epsilon move from vertex
v1 (i.e. state q0) to vertex v2 (i.e. state q2).
• Since state q2 on getting input 0 goes to state q3. Hence on duplicating the move, we will
have state q0 on getting input 0 also to go to state q3.
• Similarly state q2 on getting input 1 goes to state q4. Hence on duplicating the move, we will
have state q0 on getting input 1 also to go to state q4.
 Cont’d
• Step-3: Since vertex v1 (i.e. state q0) is a start state. Hence we will also make vertex v2 (i.e.
state q2) as a start state.
• Note that state q2 will also remain as a final state as we had initially.
• NFA after making state q2 also as a start state is:

• Step-4:Since vertex v2 (i.e. state q2) is a final state. Hence we will also make vertex v1 (i.e.
state q0) as a final state.
• Note that state q0 will also remain as a start state as we had initially.
• After making state q0 also as a final state, the resulting NFA is:
 Cont’d
• Resulting NFA (state q0 as a final state).

• The transition table for the previous resulting NFA is:

States/Input Input 0 Input 1
q0 q3 q1,q4
q1 – q0
q2 q3 q4
q3 q2 –
q4 q2 –
 Cont’d
• Example: Convert the following NFA with ε to NFA ε-free.

• Solutions: We will first obtain ε-closures of q0, q1 and q2 as follows:

1.ε-closure(q0) = {q0}   Now the δ' transition on q1 is obtained as:
2.ε-closure(q1) = {q1, q2}   δ'(q1, a) = ε-closure(δ(δ^(q1, ε),a))  
3.ε-closure(q2) = {q2}                 = ε-closure(δ(ε-closure(q1),a))  
              = ε-closure(δ(q1, q2), a)  
• Now the δ' transition on each input symbol is obtained as:
              = ε-closure(δ(q1, a) ∪ δ(q2, a))  
δ'(q0, a) = ε-closure(δ(δ^(q0, ε),a))                 = ε-closure(Ф ∪ Ф)  
              = ε-closure(δ(ε-closure(q0),a))                 = Ф  
              = ε-closure(δ(q0, a))   δ'(q1, b) = ε-closure(δ(δ^(q1, ε),b))  
              = ε-closure(q1)                 = ε-closure(δ(ε-closure(q1),b))  
              = {q1, q2}                 = ε-closure(δ(q1, q2), b)  
δ'(q0, b) = ε-closure(δ(δ^(q0, ε),b))                 = ε-closure(δ(q1, b) ∪ δ(q2, b))  
              = ε-closure(δ(ε-closure(q0),b))                 = ε-closure(Ф ∪ q2)  
              = ε-closure(δ(q0, b))                 = {q2}  
              = Ф  
 Cont’d
Now we will summarize all the computed δ' transitions
• The δ' transition on q2 is obtained as:
δ'(q0, a) = {q0, q1}  
δ'(q2, a) = ε-closure(δ(δ^(q2, ε),a))   δ'(q0, b) = Ф  
              = ε-closure(δ(ε-closure(q2),a))   δ'(q1, a) = Ф  
              = ε-closure(δ(q2, a))   δ'(q1, b) = {q2}  
              = ε-closure(Ф)   δ'(q2, a) = Ф  
              = Ф   δ'(q2, b) = {q2}  
δ'(q2, b) = ε-closure(δ(δ^(q2, ε),b))   The transition table can be:
              = ε-closure(δ(ε-closure(q2),b))  
              = ε-closure(δ(q2, b))   States a b
              = ε-closure(q2)   →q0 {q1, q2} Ф
              = {q2}  
State q1 and q2 become the final state as ε-closure of
*q1 Ф {q2}
q1 and q2 contain the final state q2.
*q2 Ф {q2}
 Exercise
• Eliminate

꓿꓿꓿꓿꓿꓿
>