Minimizing a DFA consists of merging states which perform the same action. They can be found by repeated partitoning. We will show this for an NFA in table form. Final states 2 and 4 are shown in boldface:
The first step is to partition the table into final and non-final states:
The partioning continues by partitioning out states that lead to the same partition for the same input. Here, states 1, 3, and 5 lead to the last partitioned state upon reading a "$", while state 0 does not, so we put state 0 into a new partition:
All states in the second partition go to the same partition upon reading a letter or digit, and they all go to the third partition upon reading a "$". Thus, we are done, and relabeling the state table yields:
This concludes the minimization step (see Exercise 8 )and the procedure for conversion of a regular expression to a minimal finite automation, that is, we have described a lexical analyzer generator.
Send questions and comment to: Karen Lemone