Example 2.5 : .As wo iiiontioned earlier, if A is the DFA of Example 2.1, then L{A) is the set of all strings of Os and Ts that contain a substring 01. If .4 is instead the DFA of Example 2.4, then L{A) is the set of all strings of Os and Is whose numbers of Os and Is are both even. □

2.2.6 Exercises for Section 2.2

Exercise 2.2.1: In Fig. 2.8 is a marble-rolling toy. A marble is dropped at A or B. Levers xi, хч, and x-i cause the marble to fall either to the left or to the right. Whtmever a marble encounters a lever, it causes the lever to reverse after the marble passes, so the next marble will take the opposite branch.

Figure 2.8: A marble-rolling toy

* a) Model this toy by a finite automaton. Let the inputs .4 and В rtiprtstnt the input into which tin; marble is dropped. Let acceptance corres])Ond to tlic marble exiting at D: nonacceptance represents a marble exiting at C.

\ b) Informally describe the language of the automaton.

c) Suppose that instead the levers switched before allowing the marble to pass. How would your answers to parts (a) and (b) change?

*! Exercise 2.2.2: We defined 6 by breaking the input string into any string followed by a single symbol (in the inductive part, Equation 2.1). However, we informally think of 6 as describing what happens along a path with a certain

string of labels, and if so.then it should not matter how we break the input string in the definition of 6. Show that in fact, S{q,xy) = 6{6{q,x),y) for any state q and strings x and y. Hint. Perform an induction on y.

! Exercise 2.2.3: Show that for any state q, string x, and input symbol o, 6iq,ax) = S{Siq,a),x). Hint: Use Exercise 2.2.2.

Exercise 2.2.4: Give DFAs accepting the following languages over the alphabet {0,1}:

* a) The set of all strings ending in 00.

b) The set of all strings with three consecutive Os (not necesszuily at the end).

c) The set of strings with Oil as a substring,

! Exercise 2.2.5: Give DFAs accepting the following languages over the alphabet {0,1};

a) The set of all strings such that each block of five consecutive symbols contains at least two Os.

b) The set of all strings whose tenth symbol from the right end is a 1.

c) The set of strings that either begin or end (or both) with 01.

d) The set of strings such that the number of Os is divisible by five, and the number of Is is divisible by 3,

!! Exercise 2.2.6: Give DFAs accepting the following languages over the alphabet {0,1}:

* a) The set of all strings beginning with a 1 that, when interpreted as a binary

integer, is a nmltiple of 5. For example, strings 101, 1010, and 1111 are m the language: 0, 100, and 111 are not,

b) The set of all strings that, when interpreted in reverse as a binary integer, is divisible by 5, Examples of strings in the language are 0, 10011, 1001100, and 0101.

Exercise 2.2.7: Let A be a DFA and q a particular state of A, such that 6(q, a) = q for all input symbols . Show by induction on the length of the input that for all input strings w, 6(q, w) = q.

Exercise 2.2.8: Let A be a DFA and a a particular input symbol of Л, such that for all states q of .4 we have 5(q,a) = q.

a) Show by induction on n that for all n > 0, S{q, a ) = q, whore o is the string consisting of n as.

h) Show that either jo.}* С ЦА) or {о} П Ц.А) 0.

*! Exercise 2.2.9: Let -4 = (Q, {q/}) be a DFA, and suppose that for all

a in E we have 6(qo, a) = ).

a) Show that for all w ф e we have (5(0, w) = (/tw).

b) Show that if a; is a nonempty string in L{A), then for all > 0, (i.e., T, written к times) is also in LiA).

*! Exercise 2.2.10: Consider the DF.4 with the following transition table:

Informally describe the language accepted by this DFA, and prove by inthictiou on the lengtii of an input string that your description is correct. Hint: When setting up the inductive hypothesis. It is wise to make a statemiait about what inputs get you to each state, not just what inputs get you to the accepting state.

! Exercise 2.2.11: Repeat Exerci.e 2.2.10 for the following transition table:

2.3 Nondeterministic Finite Automata

А mmdetermrnistic finite automaton (ЛТ.4) has the power to be in several states at once. This ability is often expressed as an ability to guess something about its input. For instance, when the autouiaton is used to search for certain sequences of characters (e.g., keyword.s) in a long text string, it is helpful lo guess that we are at the begiiuung of one of those strings and use a sequence of states to do nothing but check that the string appears, chiractor by characttr. Wo .shall see an example of this type of application in Section 2.4.

Before examining applications, we need to define nondeterministic finite automata and show that each one accepts a language that is also accepted by some DFA. That is, the NFAs accept exactly the regular languages, just as DF.s do. However, there are reasons to think about XFAs. They are often more succinct and easioT to design than DFAs, Moreover, while we can always convert an NF.4 to a DF.4, tin; latter may have exponentially more states than the NFA; fortunately, ca.scs of this type arc rare.