Start

Figure 2.15; This NFA has no equivalent DFA with fewer than 2 states

Now, let us see how the NF.A of Fig. 2.15 works. There is a state go that the NFA is always in, regardless of what inputs have been read. If the next input is 1, may also guess that this 1 will be the nth symbol from the end, so it goes to state gj as well as go- From state gj, any input takes to gs, the next input takes it to дз, and so on, until n - 1 inputs later, it is in the accepting state g . The formal statement of what the states of N do is:

1. JV is in state go after reading any sequence of inputs w.

2. N is in state qi, for г = 1,2,..., n, after reading input sequence w if and only if the ith symbol from the end of w is 1; that is, w is of the form xlaia2 -tti-b where the a/s are each input symbols.

We shall not prove these statements formally; the proof is an easy induction on \w\, mimicking Example 2.9. To complete the proof that the automaton

2.3.6 A Bad Case for the Subset Construction

In Example 2.10 we found that the DFA had no more states than the NFA. As we mentioned, it is quite common in practice for the DFA to have roughly the same number of states as the NFA from which it is constructed. However, exponential growth in the number of states is possible; all the 2 DFA states that we could construct from an 7i-state NFA may turn out to be accessible. The following example does not quite reacli that bound, but it is an understandable way to reach 2 states in the smallest DFA that is equivalent to an n + 1-state NFA.

Example 2.13 : Consider the NFA N of Fig. 2,15. L(jV) is the set of all strings of Os and Is such that the nth symbol from the end is 1. Intuitively, a DFA D that accepts this language must remember the last n symbols it has read. Since any of 2 subsets of the last n symbols could have been 1, if D has fewer thati 2 states, then there would be some state q such that D can be in state q after reading two different sequences of n bits, say аа-л -an and iii-2 n-

Since the sequences are different, they must differ in some position, ,чау Gj Ф bi- Suppose (by symmetry) that Oj - 1 and b, - 0. If г - 1, then q must be both an accepting state and a nonaccepting state, since oiOs - - an is accepted (the nth sjmbol from the end is 1) and bib2---bn is not. If г > 1, then consider the state p that D enters after reading г - 1 Os. Then p must be both accepting and nonaccepting, since - a 00 - 0 is accepted and

bibj.}.] bnOO 0 is not.

0, 1

The Pigeonhole Principle

In Example 2.13 we used an important reasoning technique called the pigeonhole principle. Colloquially, if you have more pigeons than pigeonholes, and each pigeon flies into some pigeonhole, then there must be at least one hole that has more than one pigeon. In our example, the pigeons are the sequences of n bits, and the pigeonholes are the states. Since there are fewer states than sequences, one state must be assigned two sequences.

The pigeonhole principle may appear obvious, but it actually depends on the number of pigeonholes being finite, Thus, it works for finite-state automata, with the states as pigeonholes, but does not apply to other kinds of automata that have an infinite number of states.

To see why the finiteness of the number of pigeonholes is essential, consider the infinite situation where the pigeonholes correspond to integers 1,2 .., Number the pigeons 0,1,2,... , so there is one more pigeon than there are pigeonholes. However, we can send pigeon г to hole г -Ы for all i > 0, Then each of the infinite number of pigeons gets a pigeonhole, and no two pigeons have to share a pigeonhole.

accepts exactly those strings with a 1 in the nth position from the end, we consider statement (2) with i = n. That says Л is in state g if and only if the nth symbol firom the end is 1. But q,i is the only accepting state, so that condition also characterizes exactly the set of strings accepted by □

2.3.7 Exercises for Section 2.3 * Exercise 2.3.1: Convert to a DFA the following NFA:

Exercise 2.3.2 : Convert to a DFA the following NFA:

Dead States and DFAs Missing Some Transitions

We have formally defined a DFA to fiave a transition from any state, on any input symbol, to exactly one state. However, sometimes, it is more convenient to design the DFA to die in situations where we know it is impossible for any extension of the input sequence to be accepted. For instance, observe the automaton of Fig. 1.2, which did its job by recognizing a single keyword, then, and nothing else. Technically, this automaton is not a DFA, because it lacks transitions on most symbols from each of its states.

However, such ал automaton is an NF.A., If we use the subset construction to convert it to a DFA, the automaton looks almost the same, but it includes a dead state, that is, a nonaccepting state that goes to itself on every possible input symbol. The dead state corresponds to 0, the empty set of states of the automaton of Fig. 1.2.

In general, we can add a dead state to any automaton that has no more than one transition for any state and input symbol. Then, add a transition to the dead state from each other state q., on all input symbols for whicli q has no other transition. The result will be a DFA in the strict sense. Thus, we shall sometimes refer to an automaton as a DFA if it has at most one transition out of any state on any symbol, rather than if it has exactly one transition.

! Exercise 2.3.3: Convert the following NFA to a DFA and informally describe the language it accepts.

! Exercise 2.3.4: Give nondeterministic finite automata to accept the following languages. Try to take advantage of nondetcrminism as much as possible,

* a) The set of strings over alphabet {0,1,..., 9} such that the fimil digit has appeared before.

b) The set of strings over alphabet (0,1,... ,9} such that the final digit has not appeared bef<ire.

c) The set of strings of Os and Is such that there are two Os separat(;d by a number of positions that is a multiple of 4. Note that 0 is an allowable multiple of 4.