Theory Of Computation

Section A

DFA Minimization using Myphill-Nerode Theorem

Algorithm

Input                DFA

Output             Minimized DFA

Step 1              Draw a table for all pairs of states (Qi, Qj) not necessarily connected directly [All are unmarked initially]

Step 2              Consider every state pair (Qi, Qj) in the DFA where Qi∈F and Qj∉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 (Qi,Qj), mark it if the pair {δ(Qi, A), δ(Qi, A)} is marked for some input alphabet.

Step 4              Combine all the unmarked pair (Qi, Qj) and make them a single state in the

Reduced DFA

.

Example

Let us use Algorithm to minimize the DFA shown below.

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

Step 2: We mark the state pairs:

Step 3: We will try to mark the state pairs, with green colored check mark, transitively. If we 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)

.

After step 3,we have got state combinations {a, b} {c, d} {c, e} {d, e} that are

unmarked.

We can recombine {c, d} {c, e} {d, e} into {c, d, e}

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}