dfa minimization using myphill-nerode theorem

algorithm

input − dfa

output − minimized dfa

step 1 − draw a table for all pairs of states (q_i, q_j) not necessarily connected directly [all are unmarked initially]

step 2 − consider every state pair (q_i, q_j) in the dfa where q_i ∈ f and q_j ∉ 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 (q_i, q_j), mark it if the pair {δ (q_i, a), δ (q_i, a)} is marked for some input alphabet.

step 4 − combine all the unmarked pair (q_i, q_j) and make them a single state in the reduced dfa.

example

let us use algorithm 2 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}

dfa minimization using equivalence theorem

if x and y are two states in a dfa, we can combine these two states into {x, y} if they are not distinguishable. two states are distinguishable, if there is at least one string s, such that one of δ (x, s) and δ (y, s) is accepting and another is not accepting. hence, a dfa is minimal if and only if all the states are distinguishable.

algorithm 3

step 1 − all the states q are divided in two partitions − final states and non-final states and are denoted by p₀. all the states in a partition are 0^th equivalent. take a counter k and initialize it with 0.

step 2 − increment k by 1. for each partition in p_k, divide the states in p_k into two partitions if they are k-distinguishable. two states within this partition x and y are k-distinguishable if there is an input s such that δ(x, s) and δ(y, s) are (k-1)-distinguishable.

step 3 − if p_k ≠ p_k-1, repeat step 2, otherwise go to step 4.

step 4 − combine k^th equivalent sets and make them the new states of the reduced dfa.

example

let us consider the following dfa −

let us apply the above algorithm to the above dfa −

• p₀ = {(c,d,e), (a,b,f)}
• p₁ = {(c,d,e), (a,b),(f)}
• p₂ = {(c,d,e), (a,b),(f)}

hence, p₁ = p₂.

there are three states in the reduced dfa. the reduced dfa is as follows −