Courses

# 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’.
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;