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.
a,b
s a s a,b … a,b s
01n
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