Minimizing Number of States of a DFA partition the set of states into two groups -G:set of accepting states -G2:set of non-accepting states ·For each new group G - partition G into subgroups such that states s and s2 are in the same group iff for all input symbols a,states s and s2 have transitions to states in the same group. 。 Start state of the minimized DFA is the group containing the start state of the original DFA. Accepting states of the minimized DFA are the groups containing the accepting states of the original DFA. CS308 Compiler Theory 18Minimizing Number of States of a DFA • partition the set of states into two groups: – G1 : set of accepting states – G 2 : set of non-accepting states • For each new group G – partition G into subgroups such that states s1 and s 2 are in the same group iff for all input symbols a, states s1 and s 2 have transitions to states in the same group. • Start state of the minimized DFA is the group containing the start state of the original DFA. • A i f h i i i d DFA h i i Accept ing states o f t he m i n i m ize d DFA are t he groups conta i n ing the accepting states of the original DFA. CS308 Compiler Theory 18