Problem Solving in Automata, Languages, and Complexity

(^54) FINITE AUTOMATA
Figure 2.34: Solution to Example 2.29.
Figure 2.35: Solution to Example 2.30.
Example 2.30 Construct an NFA accepting the set L of binary strings of an
odd length which contain the substring 00.
SoZution. A string x having a substring 00 can be written as x = ~002, for
some y, x E {O,l}. Th is string x: is of an odd length either if Iyl is even and
Izl is odd, or if lyl is odd and 1x1 is even. Thus, L can be represented as
((0 + 1) (0 + q)oo((o + I)(0 + I))(0 + 1)
+(o + l)((O + l)(O + l))oo((o + I)(0 + 1>>**
By using the method of Section 1.3, we obtain an NFA as shown in Figure
2.35. Cl
Next, we prove part (3) by showing how to construct a regular expression
from a given DFA. Our method actually works even if the given automaton is