Regular Expressions

We see that the size of the regular expression grows linearly with k—a property also shared by nondeterministic automata for this language, as we shall illustrate in Figure 9.2. In contrast, as shown in Figure 9.1, minimal DFAs for this language will grow exponentially with k. In particular, the minimal DFA for each k has 2k 1 states. The intuitive reason for this situation is that DFAs have no ability to “postpone decisions,” whereas NFAs have this ability “by keeping multiple options open.”