DFA Minimization
Peter Dixon April 26, 2021
1 DFA Minimization
Some DFAs are inefficient:
10
1
abc
1
0
is the same as
001 1 0
d
x
01
10
abc
10
This one’s not too hard to spot: there’s no way to get to x, so we can just delete it; d and a can be combined into a single state with a self-loop on 0 because it doesn’t matter if you’re in a or d, as soon as you get a 1, you go to b.
It’s less obvious that this one is the same, though:
1
b
0
0
c
0
1
1 1
a10f 0
10
e
01
10
abc
10
I made it from
d
1
by copying each state, then moving some transitions around: if a 0 could take you to b, then now it might take you to e instead. So, how do you know in general if two DFAs are the same? How do you make the smallest DFA? It’s not possible for Turing machines, but there’s a simple algorithm:
1. Remove useless states
2. Combine equivalent states
Useless states are easy to spot in a DFA (not so much in a Turing machine): if there’s no path from s to q, then q is useless. But how do we do step 2? First, we gotta figure out what makes two states equivalent. (It’s equivalence classes lol)
So two states s, t are equivalent if, for all strings z, δˆ(s, z) ∈ F ⇔ δˆ(t, z) ∈ F . We’re going to identify all non-equivalent pairs of states, by finding a z that distinguishes them. We can’t actually check “all strings z”. Fortunately, we don’t have to.
2
b
0 0
c
011 a101f
0
d
• First, we’ll build a big table of the states abcdef
a
b •c d e f
• We’ll “check” λ – in other words, we’ll mark every state in F as distin- guished from every state not in F
abcdef a
b •c d e f
• Now we check all unmarked pairs of states. We’re looking for single- character transitions that take us to states we know aren’t equivalent. For example, δ(b,1) = d and δ(c,1) = f, so b,c can’t be equivalent.
• On the other hand, c and f aren’t currently known to be different, because c,0 and f,0 go to states we don’t know to be distinct, and c,1 and f,1 also go to states we don’t know to be distinct.
• So of the remaining pairs, a,d can’t be distinguished right now, b,c are distinguished by 1, b,e can’t be distinguished right now, b,f are distin- guished by 1, c, e are distinguished by 1, and c, f are can’t be distinguished right now.
3
1
1
0
e
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
abcdef a
b •c d e f
• We check single-character transitions again and again, until no change in the table. Then we combine all the pairs that still aren’t distinguished. In this example, we’re already done, but sometimes it could take a while.
• In other words, a, d is one state; b, e is one state; c, f is one state
• b,egoestoc,f ona0,toa,dona1.
• c,f goestoc,f ona1,tob,eona0.
01
10
a,d b,e c,f
10
• What’s the runtime?
• Lazy upper bound: there are n2 pairs of states
• Worst case maximizes number of pairs we check each time. That has to go down by at least 1, so worst case is n2 +(n2 −1)+···+1 = O(n4) pairs checked
• Checking a pair means checking each symbol in Σ = O(n4|Σ|) runtime
• (It’s possible to speed it up significantly, though)
• Why does this work?
• First, why is there “a minimial DFA”?
• There has to be a “smallest number of states”, but could there be different DFAs with the same number of states?
• Not up to isomorphism
• Isomorphic: you can move the states around to make it look the same
4
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
2
• •
•
=
But why? Well, it’s all down to equivalence classes again
If M accepts L, then all the states in M correspond to equivalence classes
of L
Two minimal DFAs? Just move the states so that the states with the
same equivalence classes line up
Quick Intro to Grammars
This is a bit of a warm-up for CFGs. A grammar is another model of compu- tation, where you have a set of rules that can “produce” or “derive” strings. There are terminal symbols Σ (which we use lowercase letters for), nonterminal symbols N (upper case), and rules (a bunch of symbols on the left, a →, and a bunch of symbols on the right).
A rule looks like this: B → bB. This says “you can replace a B symbol with bB”
A grammar starts with a special start symbol S, then replaces it by apply- ing rules. It’s done when a string has only terminal symbols left. There could be multiple choices of rule; the grammar “produces” a string if there is some sequence of rule choices that ends with that string. (Kind of like nondetermin- ism.)
• Example: Σ = {a,b},N = {S}
• Onlytworules: S→aSb,S→λ
• WecandoS→aSb,thenS→aaSbb,thenS→aaλbb,sothisgrammar produces aabb
• This grammar produces L = {anbn}
• Different restrictions on the form of the rules gives different levels of power
• Regular grammar: Rules must be A → bC for some A,C ∈ N,b ∈ Σ
• Equivalent to regular languages
5
• Unrestricted grammar: Rules must have a nonterminal on the left, but could have a whole string on the left, e.g. aBcdE → FgH
• Equivalent to Turing machines
• Context-free grammar: Rules must have only a nonterminal on the left,
but whatever on the right
• Powerful enough to do nonregular stuff like {anbn}
• Useful for compilers: rules like if-block→ if (⟨bool⟩) { ⟨statement⟩ }
• Useful for human language: rules like Preposition phrase→ Preposi- tion Noun Phrase , Preposition → { a massive set of every preposition in the language}
• Originally studied for human language – what grammar is powerful enough to generate all grammatical sentences?
6