Closure Under Regular Operations

The proof tliat regular languages are closed under union was exceptionally easy because union is one of the three operations that define the regular expressions. The same idea as Theorem 4.4 applies to concatenation and closure as weU, That is:

* и L and Л/ are regular Uuiguages, then so is LM.

If L is a regular language, then so is L*.

3. Complement the accepting states of that DFA.

4. Turn the complement DFA back into a regular expression using the construction of Sections 3.2.1 or 3.2.2.

Theorem 4.5; If i is a regular language over alphabet E, then L = S* - i is also a regular language.

PROOF: Let L = L{A) for some DFA A = (Q, E,rf, 90, ) Then L = L{B), where В is the DFA (Q. y..S,qa,Q - F). That is, В is exactly like A, but the accepting states of A have become nonaccepting states of B, and vice versa. Then w is in L{B) if and only if 6iqo,w) is in Q - F, which occurs if and only \iw is not in L{A). □

Notice that it is important for tiie above proof that 5{q[i,w) is always some state; i.e., there are no missing transitions in A. If there were, then certain strings might lead neither to an accepting nor nonaccepting state of A, and those strings would be missing from both L{A) and L{B). Fortunately, wc have defined a DFA to have a transition on every symbol of E from every state, so each string leads either to a state in F or a state in Q - F.

Example 4.6: Let A be the automaton of Fig. 2.14. Recafi that DFA A accepts all and only the strings of Os and Ts that end in 01; in regular-expression terms, L{A) = (0 -b 1)*01. The complement of L[A) is therefore all strings of Os and Is that do not end in 01. Figure 4.2 sliows the automaton f(jr {0,1} - L{A). It is the same as Fig. 2.14 but with the accepting state made nonaccepting and the two nonaccepting states made accepting. □

Example 4.7: in this example, wo shall apply Theorem 4.5 to show a certain language not to be regular. In Example 4.2 we showed that the language L consisting of strings with an equal number of Os and Is and is not regular. This proof was a straightforward application of the pumping lemma. Now consider

Start

Figure 4.2: DFA accepting the complement of the language (0 + 1)*01

the language M consisting of those strings of Os and Is that have an unequal number of Os and Is.

It would be hard to use the pumping lemma to .show M is not regular. Intuitively, if we start with some string w in M, break it into w = xyz, and pump y, we might find that у itself was a string like 01 that had an equal mimber of Os and Is. If so, then for no к will xyz have an equal number of Os and Is, since xyz has an unequal number of Os and Is, and tlie numbers of Os and Is change equally as we pump y. Thus, we can never use the pumping lemma to contradict the assumption that M is regular.

However, M is still not regular. The reason is that M = L. Since the complement of the complement is the set we started with, it also follows that L = M. If M is regular, then by Theorem 4.5, L is regular. But we know L is not r(!gular, so we have a proof by contradiction that M is not regular. □

Closure Under Intersection

Now, let us consider the intersection of two regular languages. We actually have little to do, since the three boolean operations are not independent. Once we Ьале ways of performing complementation and union, we can obtain the intersection of languages L and M by the identity

LDMLuM (4.1)

In general, the intersection of two sets is the set of elements that are not in the complement of either set. That observation, which is what Equation (4.1) says, is one of DeMorgans laws. The other law is the same with union and inter.section interdianged; that \s, L U M - L Г\ M.

However, we can also perform a direct construction of a DFA for the intersection of tw regular languages. This construction, which essentially runs two DFAs in parallel, is useful in its own right. For instance, we used it to construct the automaton in Fig. 2.3 that represented the product of what two particii)aots - the bank and the store - were doing. We shall make the product construction formal in the next theorem.

Theorem 4.8: If L and M are regidar languages, then so is L П Л/.

PROOF: Let L and M be the languages of automata .Al = {ql,,L,qL:Fi,) and Am - {qm, ,ём,дм,Ем)- Notice that we are assuming that the alphabets of both automata are the same; that is, E is the union of the alphabets of L and M, if those alphabets are different. The product construction actually works for NFAs as well as DFAs, but to make the argument as simple as possible, we assume that Aj, and Ад-/ are DFAs.

For L n Af we shall construct an automaton A that simulates both A[. and A\f. The states of A are pairs of states, the first from Al and the second from Ад/. To design the transitions of Л, suppose A is in state (p, q), where p is the state of Ai and q is the state oi Am- If g is the input .symbol, we see what Аь does on input a; say it goes to state s. We also see what Am does on input o; say it makes a transition to state t. Then the next state of .4 will be (s, () In that manner, A has simulated the effect of both А/, and Am- The idea is sketclied in Fig. 4.3.

Input a

Start

Accept

Figure 4.3: An automaton simulating two other automata and accepting if and only if both accept

The remaining details are simple. The start state of A is the pair of start states of .4f. and Ад,/. Since we want to accept if and only if both automata accept, we select as the accepting states of .4 all those pairs (p, cjf) such that p is an accepting state of Al and q is an accepting state of Am. Formally, we define:

A = [qi X Qm,T.Mql:4m),Fl X Fm)

where (i((p,5),a) {Ь}.{р..а),5м{яо)).