To see why L(A) - L{Al) П L{Am}, first observe that an easy induction on \w\ proves that Ц{дь,Ям),т) = {L{qT.,w),6M{qM,w))- But A accepts ш if and only if 6{{qL,qM),w) is a pair of accepting states. That is, S[,{qi w) must be in Ft, and 6м{({а1:) must be in Fm- Put another way, w is accepted by A if and only if both Al and Am accept w. Thus, A accepts the intersection of L and AL □

Example 4.9: In Fig, 4.4 we see two DFAs. The automaton in Fig. 4.4(a) accepts all those strings that have a 0, while the automaton In Pig. 4.4(b) accepts all those strings that have a 1. We show in Fig. 4.4(c) the product of these two automata. Its states are labeled by the pairs of states of the automata in (a) and (b).

Start Q

Start

Start

Figure 4.4: The product construction

It is easy to argue that this automaton accepts the intersection of the first two languages; those strings that have both a 0 and a 1. State pr represents only the initial condition, in which we have seen neither 0 nor 1. State qr means that we have seen only Os, while state ps represents the condition that we have

seen only Is. The accepting state qs represents the condition where we have seen both Os and Is. □

Closure Under DifiFerence

There is a fourth operation that is often applied to sets and is related to the boolean operations: set difference. In ternis of languages, L - Л/, the differenca of L and M, is the set of strings that are in language L but not in language M. The regular languages are also closed under this operation, and the proof follows easily from the theorems just proven.

Theorem 4.10 : If L and M are regular languages, then so is L - M.

PROOF: Observe that L - M = L CiJl. By Theorem 4.5, M is regular, and by Theorem 4.8 L П M is regular. Th(?refore I - M is regular. □

4.2.2 Reversal

The reversal of a string O] ti * o-n is the string written backwards, that is, a\. We use ш for the reversal of string w. Thus, OOlO* is 0100, and

The reversal of a language L, written L, is the language consisting of the reversals of all its strings. For instance, if L = {001,10,111}, then L = {100,01,111}.

Reversal is another operation that preserves regidar languages; that is, if L is a regnlar language, so is L. There are two simple proofs, one ba.sed on automata and one based on regular expressions. Wt; shall give the automaton-based proof informally, and let yon fill in the details if you lik(!. We tlion prove the theorem formally using regular expressions.

Given a language L that is L{A) for some finite automaton, perhaps with nondeterminism and e-transitions, we may construct an automaton for L by:

1. Reverse all the arcs in the transition diagram for A.

2. Make the start state of A be the only accepting state for the new automaton.

3. Create a new start state pa with transitions on e to all the accepting states of .4.

The residt is an automaton that simulates A in reverse. and therefore accepts a string w if and only if .4 accepts w. Now, we prove the reversal theorem formally.

Theorem 4.11: If L is a regular language, so is L.

PROOF; Assume L is defined by regular expression E. The proof is a structural induction on the size of E. We show that there is another regular expression E such that L{E) = {1{Е)); that is, the language of E is the reversal of the language of E.

BASIS: If is e, 0, or a, for some symbol a, then E is the same as E. That is, we know {e} {e}, 0 0, and {o} = {a}.

INDUCTION: There are three cases, depending on the form of E.

1. E = Ei+E2. Then EE + E. The justification is that the reversal of the union of two languages is obtained by computing the reversals of the two languages and taking the union of those languages.

2. E = E1E2. Then E = EE. Note that we reverse the order of the two languages, as well as reversing the languages themselves. For instance, if L{Ei) {01,111} and (iJa) = {00,10}, then LiEiEh) = (0100,0110, moo, 11110}. The reversal of the latter language is

{0010,0110,00111,01111}

If we concatenate the reversals of £(2) and L{Ei) in that order, we get

{00,01}{10,111} - {0010,00111,0110,01111}

which is the same language as {L{EiE)) . In general, if a word w in L(E) is the concatenation of №1 from L{Ei) and W2 from then

3. E = E*. Then E = {EY- The justification is that any string w in L{E) can be written as W1W2 where each Wi is in L{E). But

Each is in L{E), so is m L{{EY)- Conversely, any string in L[{EY) is of the form ww --Wn, where each Wi is the reversal of a string in L(Ei]. The reversal of this string, ww -x wf, is therefore a string in L{E), which is L{E). We have thus shown that a string is in L{E) if and only if its reversal is in L{{EY)-

□

Example 4.12: Let L be defined by the regular expression (0 + 1)0*. Then is the language of (0*)(0 + l)-**, by the rule for concatenation. If we apply the rules for closure and union to the two parts, and then apply the basis rule that says the reversals of 0 and 1 are unchanged, we find that L has regular expression 0*(0 + 1). □