Dfa minimization

DFA Deterministic Finite Automata is very Famous in Theory of Computation .it often requires to build a DFA which has minimum number of states.following is the algorithm that produces a optimal DFA from a DFA.

1.Eliminate all self loops (because they cannot be reduced)

2.Make a list of all out going edges ,according to the alphabet that they have for example ,if set of alphabet contains {a,b} then u will have to list all edges starting that transit on 'a' in a list and all edges that transit on 'b' in other list.such that x->y on transist of 'a'.where x->y defines that on an read of 'a' from state x we go to y.

3.make a table that will contain no cell (x,y) where x=y

4.mark all cells whose locations define atmost one final state.

5.make order pairs of the elements of individual list individually.

6.check all pairs such that if (x,y)->(l,m) (reading a from x goes to l and y to m) and cell (l,m) is already marked then mark (x,y)7.repeat step 5 until no updation is done in the table for step 6.

8.the cells left unmarked are basically that states that could be combined and optimal DFA could be constructed.