Minimization of DFA examples and steps in toc | Myphill Nerode theorem

Minimization of DFA in theory of computation:

State Minimization of DFA in automata is the process of transforming a given DFA into an equivalent DFA that has minimum number of states. Here two DFAs are called equivalent if they recognize the same regular language. The process of minimization of DFA ensures minimal computational costs for tasks such as pattern matching. There are three classes of states that can be removed or merged from original DFA without affecting the language it accepts to minimize it.

a) Unreachable states:

These are the states that are not reachable from initial state of DFA, for any input string. They can be removed from FA without changing accepted language. They have all outgoing edges.

b) Equivalent states / Indistinguishable States:

Two states q₀_andq₁ are said to be indistinguishable or equivalent state if both run to final states or both to non-final states for all strings. Symbolically this can be represented as

1. δ (q₀, w) ∈ F and δ (q₁, w) ∈ F

2. δ (q₀, w) ∉ F and δ (q₁, w) ∉ F

c) Distinguishable States:

Two states q₀_andq₁ are said to be distinguishable or equivalent state if one state belongs to final state and other belongs to non-final state. Symbolically this can be represented as

1. δ (q₀, w) ∈ F and δ (q₁, w) ∉ F

2. δ (q₀, w) ∉ F and δ (q₁, w) ∈ F

Types of Minimization of DFA:

1) Partition Method or Equivalence theorem

2) Myphill-Nerode Theorem or Table Filling Method

A] Minimization of DFA using Partition Method or Equivalence Theorem:

If X & Y are two states in a DFA, we can combine these two states into single state {X,Y} if they are not distinguishable i.e. equivalent or indistinguishable. Two states are said to be indistinguishable or equivalent state if δ (X, w) and δ (Y, w) are going to accepting /final states or going to non-accepting /non-final states.

Symbolically this can be represented as

1. δ (X, w) ∈ F and δ (Y, w) ∈ F

2. δ (X, w) ∉ F and δ (Y, w) ∉ F

Minimization of DFA steps:

Minimization of dfa examples can be solved by using following steps

Step1: Try to delete all the states to which we cannot reach from initial state (unreachable state)

Step2: Draw state table

Step3: Find out equivalent set

Step4: Draw / Construct minimized DFA

Note:

0-Equivalent Set: Try to separate non-final states from final states.

n-Equivalent Set: We take information only from previous equivalent set i.e.(n-1)-Equivalent

Set i.e. We will check, on seeing input symbol, are they going to same state or different state.

After checking if they are in same state group in previous equivalent set, then write in same group, otherwise make separate group. Follow this procedure until we get a point where we find “No change” in the state group.

B] Minimization of DFA using Myphill-Nerode Theorem or Table Filling Method:

Minimization of DFA steps:

Minimization of dfa examples can be solved by using following steps:

Step1: Draw a table for all pairs of states(P,Q)

Step2: Mark all pairs where P ∈ F and Q ∉ F

Step3: If there are any unmarked pairs (P,Q) such that [δ (P, x) , δ (Q, x)] is marked then mark [P,Q] where ‘x’ is an input symbol. Repeat this until no more markings can be made

Step4: Combine all the unmarked pairs and make them a single state in minimized DFA.