Myhill Nerode Theorem||Minimization of DFA using Myhill Nerode Theorem

To minimize a DFA  in this theorem check whether two states are equivalent or not.If two states are equivalent then we merge these two states into one state in order to minimize the number of states of a DFA.If a finite automata has not minimum number of states then it results in wastage of the resources and often results in bad performance.

Myhill Nerode Theorem used for minimize DFA

Step1:- Create table for all pairs of state.

Step2:-Mark all pair while Pદ F and Q∉F.

Step3:- if there are any unmarked state pair  δ(P,x),δ(Q,x) is marked then mark (P,Q) state.Repeat until no more marking can be made.

Step4:-Combine all the unmarked pairs and make single state in minimize DFA.

Example:-

Minimize the DFA using Myhill -Nerode Theorem.

Solution:-

Step1:-Create a table all pair of state.

mark diagonal with *.

Step2:-mark pair (C,A) and (C,B) and (E,C) because in pair(C,A) C is final state and A ia not final state so mark it. Same as (C,B) and (E,C).

 Step3:-(B,A) unmark so

          (B,a)=B

          (A,a)=B

          (B,b)=E

          (A,b)=C

     Get state pair (B,B) and (E,C) and (E,C) is mark so mark pair (B,A).

  Next pair(E,A)

        (E,a)=B

        (A,a)=B

        (E,b)=E

        (A,b)=E

    (B,B) and (E,E) is diagonal so (E,A) is unmarked.

  Next pair (E,B)

    (E,a)=B

    (B,a)=B

    (E,b)=E

    (B,b)=C

Get pair (B,B) and (E,C) and pair (E,C) is marked so marked pair (E,B).

So left pair (E,A) which is unmark so merge both state (E,A). After merge both state (E,A) get minimized DFA.

Using Myhill Nerode Theorem minimization DFA.Reduce state four to three.