1. Closure under Union

If L and M are regular languages, so is L UM.

Proof : Let L and M be the languages of regular expressions R and S, respectively.

Then R+S is a regular expression whose language is L U M

2. Closure under Concatenation and Kleene Closure

The same idea can be applied using Kleeneclosure :

RS is a regular expression whose language is LM.

R* is a regular expression whose language is L*.

3. Closure under intersection

If L and M are regular languages, so is L ∩ M

Proof : Let A and B be two DFA’s whose regular languages are L and M respectively.

Now, construct C, the product automation of A and B. Make the final states of C be the pairs consisting of final states of both A and B.

4. Closure under Difference

If L and M area regular languages, so is L-M, which means all the strings that are in L , but not in M. Proof : Let A and B be two DFA’s whose regular languages are L and M respectively. Now, construct C, the product automation of A and B. Make the final states of C be the pairs consisting of final states of A, but not of B. The DFA’s A-B and C-D remain unchanged, but the final DFA varies as follows:

5. Closure under Concatenation

The complementof a language L (with respect to an alphabet Σ such that Σ* contains L) isΣ* – L Since Σ* is surely regular, the complement of a regular language is always regular

6. Closure under Reversal

Given language L, LR is the set of strings whose reversal is in L

L = {0, 01, 100}; LR = {0, 10, 001}

Basis: If E is a symbol a, ε, or ∅, then ER = E.

Induction: If E is

• F+G, then ER = FR + GR.

• FG, then ER = GRFR

• F, then ER = (FR)

  Let E = 01* + 10*.

$E_R = (01* + 10*)^R = (01*)^R + (10*)^R$

$= (1*)^R 0^R + (0*)^R 1^R$

$= (1^R)*0 + (0^R)*1$

$= 1*0 + 0*1$

7. Closure under homomorphism

Definition of homomorphism:

A homomorphism on an alphabet is a function that gives a string for each symbol in that alphabet.

Closure property:

If L is a regular language, and h is a homomorphism on its alphabet, then h(L) = {h(w) | w is in L} is also a regular language.

Proof: Let E be a regular expression for L.

Apply h to each symbol in E.

Language of resulting RE is h(L)

Example:

Let h(0) = ab; h(1) = ε.

Let L be the language of regular expression 01* + 10*.

Then h(L) is the language of regular expression abε* + ε(ab)*

abε* + ε(ab)* can be simplified.

ε* = ε, so abε* = abε.

ε is the identity under concatenation.

That is, εE = Eε= E for any RE E.

Thus, abε* + ε(ab)* = abε + ε(ab)*

= ab + (ab)*.

Finally, L(ab) is contained in L((ab)), so a RE for h(L) is (ab)

8. Closure under inverse homomorphism

a. Start with a DFA A for L.

b. Construct a DFA B for h-1(L) with: - The same set of states.

• The same start state.

• The same final states.

• Input alphabet = the symbols to which homomorphism h applies