expression [tiiQi] + [даОгз] + where the pairs ид, range over all pairs in S X 0 such that Oi) = qi. Then let Li П i(EiT-). Since EiT* is a regular expression denoting all strings in T that begin with the start state {treat T in the regular expression as the sum of its symbols), L-i is all strings that are formed by applying to language M and that have the start state as the first component of its first symbol; i.e.. it meet.s condition (1).

To enforce condition (2), it is easier to subtract from L2 {using the set-difference operation) all those strings that violate it. Let E2 be the regular expression con.sisting of the sum (union) of the concatenation of all pains of symbols that fail to match; that is, pair,? of the form [prtjfrfc.*] where q Ф r. Then T*E2T is a regular expression denoting all strings that fail to meet condition (2),

We may now define L3 - L2 - L{T*E-2T*]. The strings of L3 satisfy condition (i) because strings in L2 must begin with the start symbol. They satisfy condition (2) because the subtraction of L{T E2T*) removes any string that violates that condition. Finally, they satisfy condition (3), that the last state is accepting, because we started with only strings in il/, all of which lead to acceptance by A. The effect is that consists of the strings in M with the states of the accepting computation of that string embedded as part of each symbol. Note that L>, is regular because it is the result of starting with the regulai language Л/, and applying operations - inverse homomorphism, intersection, and set difference - that yield regul;u sets when applied to regular sets.

Recall that our goal was to at;cept only tho.se strings in M that visited every state in their accepting computation. We may enforce this condition by additional applications of the set-difference operator. That is, for each state q, let Eq be the regular- expression that is the simi of all the symbols in T such that q appears in neither its first or last position. If we subtract L{E*) from L3 we have those strings that are an accepting computation of .4 and that visit state q at least once. If we subtract from all the languages I(F*) for q in Q, then we have the accepting computations of A that visit all the states. Call this language Ьц. By Theorem 4.10 we know L is also regular.

Our final step is to construct L from L.\ by getting rid of the state components. That is, L - h{L.\). Now, L is the set of strings in that are accepted by .4 and that vi.sit each tate of A at least once during their acceptance. Since regular languages are closed under homomorphisms, we conclude that L is regnlar. □

4.2.5 Exercises for Section 4.2

Exercise 4.2.1: Suppose h is the homomorphism from the alphabet {0,1,2} to the alphabet {aji} defined by: Л,(0) a\ Л(1) - nb, and h{2) bo.

* a) What is ?г(0120)?

b) What is ?i(21120)?

* c) If L is the language L(01*2), what is ft(L)7 d) If L is the language L{0 + 12), what is h{L)?

* e) Suppose L is the language {ababa}, that is, the language consisting of

only the one string ababa. What is /t~(L)?

! f) If L is the language L(a(ba)*), what is WL)!

*-\ Exercise 4.2.2: If L is a language, and a is a symbol, then Lja, the quotient of L and a, is the set of strings w such that wa is in L. For example, if L - {u,aab,baa}, then Lja - {e,ba}. Prove that if L is regular, so is Lja. Hint: Start with a DFA for L and consider the set of accepting states.

! Exercise 4.2.3: Lf L is a language, and о is a symbol, then a\L is the set of strings w such that aiv is in L. For example, if L - {a.aab.baa}, then a\L ~ {f-.ab}. Prove that if L is regular, so is a\L. Hint: Remember that the regular languages are closed under reversal and under the quotient operation of Exercise 4.2.2.

! Exercise 4.2.4: Which of the following identities are true?

a) {L/a)a - L (the left side represents the concatenation of the languages L/a and {a}).

b) a{a\L) = L (again, concatenation with {a}, this time on the left, is intended).

c) {La)/a = L.

d) a\(aL)L.

Exercise 4.2.5: The operation of Exercise 4.2.3 is sometunes viewed as a derivative, and a\L is written These derivatives apply to regular expressions in a mariner similar to the way ordinary derivatives apply to arithmetic expressions. Thus, if i? is a regular expression, we shall use to mean the same as

f>ifi = b(fi).

a) Showthat = f + f.

*! b) Give the rule for the derivative of RS. Hird: You need to consider two cases: if L{R) does or does not contain e. This rule is not quite the same as the product rule for ordinary derivatives, but is similar.

! c) Give the rule for the derivative of a closure, i.e.,

d) Use the rules from (a)- (c) to find the derivatives of regular expression (0 + 1)*011 with respect to 0 and 1.

* e) Characterize those languages L for which = 0.

*! f) Characterize those languages L for which = L.

! Exercise 4.2.6: Show that the regular languages are closed under the following operations:

a) min{L) = {w \ w ism L, but no proper prefix of w is in L}.

b) max{L) = {w \ w is in L and for no x other than e is wx in L}.

c) init(L) - {w I for some x, wx is in L}.

Hint: Like Exercise 4.2.2, it is easiest to start with a DFA for L and perform a construction to get the desired language.

! Exercise 4.2.7: li w - fliC2--an and x - bib-bm are strings of the same length, define alt{w, x) to be the string in which the symbols of w and x alternate, starting with w, that is, aibia2b2 anb . If L and M are languages, define alt{L, M) to be the set of strings of the form altiw, x), where tv is any .string in L and x is any string in AI of the same length. Prove that if L and M are regular, so is alt[L,M).

*!! Exercise 4.2.8: Let L be a language. Define haif{L) to be the set of first halves of strings in L, that is, {w \ for some x such that a: - \w\, we have wx in L). For example, if L = {e,0010,011,010110} then half{L) = {e, 00,010}. Notice that odd-length strings do not contribute to half{L). Prove that if L is a regular language, so is half{L).

!! Exercise 4.2.9: We can generalize Exercise 4.2.8 to a number of functions that determine how much of the string we take. If / is a function of integers, define f{L) to be {ш I for some x, with \x\ - f{\iv\), we have wx in L}. For instance, the operation Ло corresponds to / being the identity function /(ri) - n, since half{L) is defined by having \x\ = \w\. Show that if L is a regular language, then so is f{L), if / is one of the following functions:

a) f{n) - 2n (i.e., take the first thirds of struigs),

b) f{n) = n? (i.e., the amount we take has length equal to the square root of what we do not take.

c) /{) = 2 {i.e., what we take has length equal to the logarithm of what we leave).

!! Exercise 4.2.10: Suppose that L is any language, not necessarily regular, whose alphabet is {0}; i.e.. the strings of L consist of Os only. Prove that L* is regular. Hint: At first, this theorem sounds preposterous. However, an example will help you see why it is true. Consider the language L - {0 * is prime}, which we know is not regidar by Example 4.3. Strings 00 and ООО are in L, since 2 and 3 are both primes. Thus, if j > 2, we can show is in i*. If j is even, use i/2 copies of 00, and if j is odd, use one copy of ООО and [j - 3)/2 copies of 00. Thus, L* = ООО*.