! Exercise 4.1.2: Prove that the following are not regular languages.

* a) {0 I n is a perfect square}.

b) {0 I n is a perfect cube}.

c) {0 I n is a power of 2}.

d) The set of strings of Os and Is whose length is a perfect square.

e) The set of strings of Os and Is that are of the form ww, that is, some string repeated.

f) The set of strings of Os and Is that are of the form ww, that is, some string followed by its reverse. (See Section 4.2.2 for a formal definition of the reversal of a string.)

g) The set of strings of Os and Is of the form ww, where W is formed from w by replacing all Os by Is, and vice-versa; e.g.. Oil = 100, and 011100 is an example of a string in the language.

hj The set of strings of the form ш;1 , where w is a string of Os and Is of length n.

! Exercise 4.1.3: Prove that the following are not regular languages.

a) The set of strings of Os and Is, beginning with a 1, such that when interpreted as an integer, that integer is a prime.

b) The set of strings of the form OP such that the greatest common divisor of г and j is 1.

! Exercise 4.1.4: When we try to apply the pumping lemma to a regular language, the adversary wins, and we cannot complete the proof. Show what goes wrong when we choose L to be one of the following languages:

* a) The empty set.

* b) {00,11}. *c) (00-Hll)*.

d) 01*0*1.

4,2 Closure Properties of Regular Languages

In this section, \ve shall prove several theorems of the form if certain languages are regular, and a language L is formed from them by certain operations (e.g., L is the union of two regular languages), then L is also regular. Those theorems are often called closure properties of the regular languages, since they show that the class of regular languages is closed under the operation mentioned, Closun; properties express the idea that when one (or several) languages are regular, then certn related languages are also regular. They also serve as an interesting illustration of how the equivalent representations of the regular languagtS (automata and regular expressions) reinforce each other in our understanding of the class of languages, since often one representation is far better than the others in supporting a proof of a closure property. Here is a summary of the principal closure properties for regular languages:

1. The union of two regular languages is regular.

2. The intersection of two regular languages is regular.

3. The complement of a regular language is regular.

4. The difference of two regular languages is regular.

5. The reversal of a regular language is regular.

6. The closure (star) of a regular language is regular.

7. The concatenation of regular languages is regular,

8. A homomorphism (substitution of strings for symbols) of a regular language is regular.

9. The inverse homomorphism of a reguhu: language is regular,

4.2.1 Closure of Regular Languages Under Boolean Operations

Our first closure properties are the three boolean opc>rations: union, intersection, and complementation:

1. Let It and M be languages over alphabet S. Then L U M is the language that contains аИ strings that are in either or both of L and M.

2. Let L and M be languages over alphabet E. Then L П M is the language that coiLtains all strings that are in both L and M.

3. Let L be a language over alphabet S. Then L, the complement of L, is the set of strings in E* that are not in L.

It turns out that the regular languages are closed under all three of the boolean operations. The proofs take rather different approaches though, as we shall see.

What if Languages Have Different Alphabets?

When we take the* miiou or iiit(;rsection of two languages L and M, Lhey might have different alphabets. For example, it is ])oHsible that Li С { , b} whilp Ln с {b.,C-d}. However, if a language l consists of strings with

syjuliol.s in S, tlien we can also tliiiik of Z. a5 a language over utiy finite alphabet that is a .sui>erset of S. Tims, for example, we can think of both L\ and L2 above as being languages over alphabet {u, 6, r, f/}. The fact that none of Lis stnngs contain symbols с or is irrehwant, as is the fact that Los strings will not contain .

Likewise, when taking the complement of a language L that is a suKset of for some alphabet , we may choose to take the complement with respect to some alphabet T2 that is a superset of Si. If so, then the conii)ltment of L will be S.j - L; that is, the complement of L with respect to S) includes (among other strings) all those strings in S2 that have at least one symbol that is in bnt not in . Had we taken the complement of L with r(;spect to Hi, then no strhig with symbols in So-Si would be in L. Thus, to be strict, we should always state the alphabet with respect to which a complement, is taken. However, often it is olnious which alphabet is meant; e.g., if L is defined by an automaton, then the specification of that automaton includes the alphabet. Thus, we shall often speak of the complement without specifying the alphabet.

Closure Under Union

Theorem 4.4: If L and M are regular languages, then so is I. U M.

PROOF: This proof is simple. Since L and M are regular, they have regular expressions; .say L = L[R) and M L{S). Then LU M = L{R + S) by the definition of the + operator for regular expressions. □

Closnrc Under Complementation

The theorem for union wfus made very easy by the use of the regular-expression representation for the languages. How(>ver, let us next consider complc;riK?n-tation. Do you see how to take a regular expression and change it into one that defines the complement language? Well neither do we. However, it can be done, because as we shall see in Theorem 4.5, it is ea.sy to start with a DFA and construct a DF.A that accepts the complement. Thus, starting with a regular expression, we could find a regular expression for its complement as follows:

1. Convert the regular expression to an f-NFA.

2. Convert that f-NFA to a DFA bv the subset construction.