blow_up.dvi
An example of exponential blow-up in
determinization
Prakash Panangaden
16th September 2011
We fix the alphabet Σ = {a, b}. Consider the problem of recognizing strings
where the nth character from the end is an a. The following NFA does the
job.
s0 s1 . . . sn
a a, b a, b
a, b
Any deterministic automaton will take at least 2n states. Suppose that a
DFA M has fewer than 2n states. Consider all possible strings of length
n: there are 2n such strings. Thus if we see where the machine ends up
after processing each of these strings there must be two strings that end up
with the machine in the same state; let these two strings be called x and y.
Suppose that they are the same up to position k and in position k, x has an
a whereas y has a b. Consider the new strings x′ = xak−1, y′ = yak−1. Now
clearly x′ should be accepted whereas y′ should be rejected. But at the end
of processing either x or y the machine is in the same state and then both
strings x′ and y′ are identical there after. Since it is a DFA the transitions
must be identical so it has to treat the two strings x′ and y′ the same way.
This is a contradiction.
1