Page 1 Minimizing the Number of States in a DFA Smaller is better! Page 2 Minimizing the Number of States in a DFA Smaller is better! Minimal DFA ? Given any DFA, there is an equivalent DFA containing the minimum number of states ? The minimal DFA is unique ? It is possible to directly obtain the minimal DFA from any DFA ? The algorithm presented here is adapted from Aho, Sethi, and Ullman. Page 3 Minimizing the Number of States in a DFA Smaller is better! Minimal DFA ? Given any DFA, there is an equivalent DFA containing the minimum number of states ? The minimal DFA is unique ? It is possible to directly obtain the minimal DFA from any DFA ? The algorithm presented here is adapted from Aho, Sethi, and Ullman. Minimal DFA Algorithm 1 ? The algorithm starts by partitioning the states in the DFA into sets of states that will ultimately be combined into single states. ? The first partitioning creates 2 sets: – One set contains all the accepting states – The other set contains all the nonaccepting states ? The process now goes through one or more iterations where it considers the transitions on each character of the alphabet Page 4 Minimizing the Number of States in a DFA Smaller is better! Minimal DFA ? Given any DFA, there is an equivalent DFA containing the minimum number of states ? The minimal DFA is unique ? It is possible to directly obtain the minimal DFA from any DFA ? The algorithm presented here is adapted from Aho, Sethi, and Ullman. Minimal DFA Algorithm 1 ? The algorithm starts by partitioning the states in the DFA into sets of states that will ultimately be combined into single states. ? The first partitioning creates 2 sets: – One set contains all the accepting states – The other set contains all the nonaccepting states ? The process now goes through one or more iterations where it considers the transitions on each character of the alphabet Minimal DFA Algorithm 2 ? Iterate until no further partitioning is possible: – For each set G of states in partition ?, consider the transitions for each input symbol a from any state in G. – Two states s and t belong in the same subgroup iff for all input symbols a, states s and t have transitions into states in the same subgroup of ?. – Replace G in ? by the set of subgroups formed. Page 5 Minimizing the Number of States in a DFA Smaller is better! Minimal DFA ? Given any DFA, there is an equivalent DFA containing the minimum number of states ? The minimal DFA is unique ? It is possible to directly obtain the minimal DFA from any DFA ? The algorithm presented here is adapted from Aho, Sethi, and Ullman. Minimal DFA Algorithm 1 ? The algorithm starts by partitioning the states in the DFA into sets of states that will ultimately be combined into single states. ? The first partitioning creates 2 sets: – One set contains all the accepting states – The other set contains all the nonaccepting states ? The process now goes through one or more iterations where it considers the transitions on each character of the alphabet Minimal DFA Algorithm 2 ? Iterate until no further partitioning is possible: – For each set G of states in partition ?, consider the transitions for each input symbol a from any state in G. – Two states s and t belong in the same subgroup iff for all input symbols a, states s and t have transitions into states in the same subgroup of ?. – Replace G in ? by the set of subgroups formed. Minimal DFA Algorithm 3 ? Choose one state in each group of the partition ? as the representative for that group. The representatives will be the states of the reduced DFA M’. ? The start state of M’ will be the group that contains the start state of the original DFA. ? Any group that contains an accepting state from the original DFA will be an accepting state of the minimal DFA M’.Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!