Closure under Union

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

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

Closure under Concatenation and Kleene Closure

The same idea can be applied using Kleene closure :

RS is a regular expression whose language is LM.

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

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.

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:

Closure under Concatenation

The complement of 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

Closure under Reversal

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

$L = {0, 01, 100}; L_R = {0, 10, 001}$

$Basis: If E is a symbol a, ε, or ∅, then E^R = 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*)^R0^R + (0*)^R1^R$

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

= 10 + 01

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)

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