Minimal DFA - compiler DFA IT & Software Notes | EduRev

IT & Software : Minimal DFA - compiler DFA IT & Software Notes | EduRev

 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!

Related Searches

Extra Questions

,

Minimal DFA - compiler DFA IT & Software Notes | EduRev

,

Free

,

Semester Notes

,

study material

,

shortcuts and tricks

,

Viva Questions

,

pdf

,

Minimal DFA - compiler DFA IT & Software Notes | EduRev

,

video lectures

,

practice quizzes

,

Important questions

,

Summary

,

Minimal DFA - compiler DFA IT & Software Notes | EduRev

,

Exam

,

Previous Year Questions with Solutions

,

mock tests for examination

,

Sample Paper

,

past year papers

,

ppt

,

Objective type Questions

,

MCQs

;