Algorithm for DFA Minimization using Myphill-Nerode Theorem

Input : DFA

Output:  Minimized DFA

Step 1: Start

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

Step 3:  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 4:  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 5: Combine all the unmarked pair (Qi, Qj) and make them a single state in the reduced DFA.

Step 6:Stop

Leave a Reply