Problem Solving in Automata, Languages, and Complexity

2.4 Converting an NFA to a DFA 45

0 a (b)

0 C

Figure 2.27: Three NFA’s of Exercise 2,

(c) The set of binary strings that contain either a substring 010 or a

substring 101, and end with 111 or 000.

(d) The set of binary strings of which the (3n)th symbol is 0 for each

n > - 1.

(e) The set of binary strings x of length 3n for some n > 1, such that,

for each 1 < - k - < n, at least one of the (3k - 2)nd, (3k - 1)st and

(3k)th symbols of IX: is 0.

(f) The set {O”lO”lO~ (^1) q E nm (mod 5)).

4. Prove that the new initial state s and the final state f in the construction
   of Example 2.22 are necessary. That is, find NFA’s A41 and A& such that
   the NFA’s A&i and AI: of Figure 2.28 have the property L(Mi) # L(I&)
   and L(Mi) # L(Mz).

2.4 Converting an NFA to a DFA

Although it is easier to construct, a nondeterministic machine is just an ideal-
ized machine which cannot be efficiently implemented in practice, since a real
machine can only follow one computation path at a time. For the finite state
automata, it is fortunate that there is a simple procedure to convert an NFA
to an equivalent DFA which accepts the same language. Thus, the notion of
NFA’s can be turned into practical use.