0
Explain the closure properties of regular languages

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: May 2014

0  upvotes
0

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.

enter image description here
enter image description here

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:

enter image description here

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

0  upvotes
Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More