Dfa minimization

From Wikipedia, the free encyclopedia

This article may require cleanup to meet Wikipedia's quality standards. Please improve this article if you can. (May 2008)

This article does not cite any references or sources. (May 2008) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

This article or section needs to be wikified to meet Wikipedia's quality standards. Please help improve this article with relevant internal links. (May 2008)

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.

This article is uncategorized. Please categorize this article to list it with similar articles. (May 2008)