DFA Minimization

DFA Minimization Notes

1. Minimize the given DFA

Solution:

0^' equivalence: Start by distinguishing final and non-final: {q1,q3}, {q2,q4,q5,q6}

1'st equivalence: Distinguish states within the groups, to get the next partition:

{q1,q3}, {q4,q6}, {q5}, {q2}

b distinguishes q2, q4:

δ(q2,b) ∈ {q1,q3}, δ(q4,b) ∈ {q2,q4,q5,q6}

b distinguishes q2, q5:

δ(q2,b) ∈ {q1,q3}, δ(q5,b) ∈ {q2,q4,q5,q6}

a distinguishes q4, q5:

δ(q4,a) ∈ {q1,q3}, δ(q5,a) ∈ {q2,q4,q5,q6}

neither a nor b distinguishes (q4,q6)

2^'nd equivalence: We cannot split the two non-singleton groups further, the algorithm terminates.

The minimal DFA has start state {q1,q3}, single final state {q4,q6} with transition function:

Note: How equivalence classes are decided??

The construction of the equivalence classes starts like this:

p and q are 0-indistinguishable if they are both final or both non-final. So we start the algorithm with the states divided in two partitions: final and non-final.
within each of these two partitions: p and q are 1-distinguishable if there is a symbol σ so that δ(p,σ) and δ(q,σ) are 0-distinguishable, i.e. one is final and the other not. By doing so we further partition each group into sets of 1-indistinguishable states.
The idea then is to keep splitting these partitioning sets as follows:
p and q within a partition set are k-distinguishable if there is a symbol σ so that δ(p,σ) and δ(q,σ) are (k-1)-distinguishable.
At some point, we cannot subdivide the partitions further. At that point terminate the algorithm, because no further step can produce any new subdivision. When we terminate, we have the indistinguishability equivalence classes which form the states of the minimal DFA. The transition from one equivalence class to another is obtained by choosing an arbitrary state in the source class, applying the transition and then taking the entire target class as the target state.

0Comment

thumbs up down

Notes of Minimization of DFA using Myhill-Nerode Theorem

A short notes from the above video lecture.

Minimization steps :

1. Make the table as shown in the procedure.

2. Marking into the table:(Iteration 1)

if you are looking into two stages A and B, if only one of them is final, put a mark into that field in the table.

if both stages are final or no one is final don't do anything into the table.

3. Iteration 2:

for all unmarked field do one more iteration, and if obtained state sequence is marked in the previous iteration, then marked the previous filed on to which operation is performed.

Do this until you are done with every state field.

4. combine all the unmarked pair and put the transaction as accordance.

0Comment

thumbs up down

Minimization of DFA | Steps to minimize the DFA

MINIMISATION OF DFA is the procedure through which we can obtain minimized DFA which consists of a minimum number of states.

There are two classes of states that can be removed or merged from the original DFA without affecting the language it accepts to minimize it.

Unreachable states are the states that are not reachable from the initial state of the DFA, for any input string.
Nondistinguishable states are those that cannot be distinguished from one another for any input string.

Let p and q be two states then (p,q) are equivalent states and this two states in a DFA can be replaced by a single state if $\delta (p,w)\epsilon F\Rightarrow \delta (q,w)\epsilon F$ where state p on seeing input a goes to final state implies that state q also goes to the final state.

STEPS TO MINIMIZE DFA:

Remove the unreachable states from DFA.
Draw the transition table for the remaining states.
Now, divide rows of transition table in 2 states as Set-1 consists of all the non-final states and Set-2 contains final states.
Search for similar rows(for different sets deriving output states are same on same input symbol)
Merge them and repeat the procedure for the rest of the table.
Draw the transition diagram for minimized DFA.

EXAMPLE:

Step-I: Delete a state which is unreachable from the initial state. In this problem, there is no dead state, therefore, proceed to next step.

Step-II: Draw the transition table.

	a	b
q₀	q₁	q₂
q₁	q₁	q₃
q₂	q₁	q₂
q₃	q₁	q₄
q₄	q₁	q₂

Step-III: Try to find out equivalent sets(sets of all non final states and final states)

[q_0,q_1,q_2,q₃][q₄] (separating final and non-final states into different sets)
[q₀q₂][q_1,q₃][q₄] (q₀ and q₂ equivalent states)
[q₀q₂][q₁][q₃][q₄] (q₁and q₃will be in different set as they are not equivalent)

Newly formed states after minimizing the DFA are q₀q₂, q₁, q₃, q_4.

Step-IV: Draw the minimized DFA.

0Comment

thumbs up down