Closure Properties of Regular Languages

Closure Properties of Regular Languages  

AU: May-06,10,13,14, Dec.-07.08,10,12,13,17, Marks 8

If certain languages are regular and language L is formed from them by certain operations (such as union or concatenation) then L is also regular. These properties are called closure properties of regular languages. Such languages represent the class of regular languages which is closed under the certain specific operations.

The closure properties express the idea that when one or many languages are regular then certain related languages are also regular. The closure properties of regular languages are as given below.

1. The union of two regular languages is regular.

2. The intersection of two regular languages is regular.

3. The complement of a regular languages is regular.

4. The difference of two regular languages is regular.

5. The reversal of a regular languages is regular.

6. The closure operation on a regular language is regular.

7. The concatenation of regular language is regular.

8. A homomorphism of regular languages is regular.

9. The inverse homomorphism of regular language is regular.

Theorem 1: If L₁ and L₂ are two languages then L₁ U L₂ is regular.

Proof: If L₁ and L₂ are regular then they have regular expression L₁ = L (R₁) and L₂ = L (R₂) Then L₁ U L₂ = L (R₁+ R₂) thus we get L₁ U L₂ as regular language. (any language given by some regular expression is regular).

Theorem 2: The complement of regular language is regular. AU May-14, Marks 6, Dec.-08, Marks 2

Proof : Consider L₁ be regular language which is accepted by a DFA M = (Q, Σ, δ, q₀, F) The complement of regular language is L₁ which is accepted by M' = (Q, Σ, δ, q₀, Q - F) That means M is a DFA with final states ϵ F and M' is a DFA in which all the non-final states of M become final. In other words, we can say that the strings that are accepted by M are rejected by M' similarly, the strings rejected by M are accepted by M'.

Thus as L₁ is accepted by DFA M', it is regular.

Theorem 3: If L₁ and L₂ are two regular languages then L₁∩ L₂ is regular. AU: Dec.-07, 08, Marks 4

Proof: Consider that languages L₁ is regular. That means there exists some DFA M₁ that accepts L₁. We can write M = (Q₁, Σ, δ₁, q₁, F₁) Similarly being L₂ regular there is another DFA M₂ (Q₂, Σ, δ₂, q₂, F₂)

Let, L be the language obtained from L₁ ∩ L₂. We can the simulate  M = (Q, Σ, δ, q, F)

where

Q = Q₁ ∩ Q₂

δ = δ₁ ∩ δ₂ a mapping function derived from both the DFAS.

q ϵ Q which is initial state of machine M.

F = F₁ ∩ F₂, the set of final states, which is common for M₁ and M₂ both.

It is clear that there exists some DFA which accepts L₁ ∩ L₂ i.e. L. Hence L is a regular language. This proves that if  L₁ and L₂ are two regular languages then L₁ is regular. In other words the regular language is closed under intersection.

Theorem 4: If L₁ and L₂ are two regular languages then L₁ - L₂ is regular.

Proof: The L₁ - L₂ can also be denoted as L1 U Ḹ₂

Consider L₁ be regular language which is accepted by DFA M =(Q,Σ,δ,q₀,F) The complement of regular language L₁ is Ḹ₁ which is accepted by M'=(Q,Σ,δ,q₀,Q-F) That means M is a DFA with final state's set F and M' is a DFA in which all the non final states of M become final states and all the final states of M become non-final states. Thus L₁ and Ḹ₂ are two regular languages. That also means: these languages are accepted by regular expressions. If L₁ = L(R₁) and Ḹ₂ = L(R`<sub>2</sub>). Then L<sub>1</sub> U Ḹ<sub>2</sub> = L (R<sub>1</sub> + R`₂). This ultimately shows that L₁ U Ḹ₂ is regular. In other words L₁ – L₂ is regular. Thus regular languages are closed under difference.

Theorem 5: The reversal of a regular languages is regular. AU: Dec.-07, 08, Marks 4

Proof: Reversal of a string means obtaining a string which is written from backward that is w is denoted as reversal of string w. That means L (w^R) = (L(w))^R. This proof can be done with basis of induction.

Basis: If w= ε or ϕ then w^R is also ε or ϕ

i.e. (ε)^R = ε and (ϕ)^R = ϕ

Hence L(w^R) is also regular.

Induction :

Case 1: If w = w₁+ w₂ then

w = (w₁)^R + (w)^R

As the regular language is closed under union. Then w is also regular.

Case 2: If w = w₁ + w₂

Consider w₁ = (ab, bb)

and w₂ = (bbba, aa)

The w^R₁ = (ba, aa)

w^R₂ = (aaab, bb) then

w – w^R₁ w^R₂

(ba, aa, aaab, bb) is also regular. Thus given language is regular one.

Theorem 6: The closure operation on a regular language is regular.

Proof: If language L₁ is regular then it can be expressed as L₁ = L(R₁) Thus for a closure operation a language can be expressed as a language of regular expressions. Hence L₁ is said to be a regular language.

Theorem 7: If L₁ and L₂ are two languages then L₁ L₂ is regular. In other words regular languages are closed under concatenation.

Proof: If L₁ and L₂ are regular then they can be expressed as L₁ = L(R₁) and L₂ = L(R₂) Then L₁ L₂ = L(R₁ R₂) thus we get a regular language. Hence it is proved that regular languages are closed under concatenation.

Theorem 8: A homomorphism of regular languages is regular.

Proof: The term homomorphism means substitution of string by some other symbols. For instance the string "aabb" can be written as 0011 under homomorphism. Clearly here, a is replaced by 0 and b is replaced by 1. Let Σ is the set of input alphabets and Γ be the set of substitution symbols then Σ^* → Γ^* is homomorphism. The definition of homomorphism can be extended as

Let, w = a₁ a₂ ... a_n

h(w) = h(a₁) h(a₂) ... h(a_n)

If L is a language that belongs to set Σ, then the homomorphic image of L can be defined as:

h(L) = {h(w): w ϵ L}

To prove that if L is regular h(L) is also regular consider following example -

Let, Σ = {a, b} and w = abab

Let h(a) = 00

and h(b) = 11

Then we can write h(w) = h(a) h(b) h(a) h(b)

= 00110011

The homomorphism to language is applied by applying homomorphism on each string of language.

If L = ab^*b then,

L = {ab, abb, abbb, abbbb, ...)

Now h(L) = (0011, 001111, 00111111, 0011111111, ...)

h(L) = 00 (11)* As it can be represented by a regular expression, it is a regular language. Hence it is proved that if L is regular then h(L) is also regular. In other words, family of regular languages is closed under homomorphism.

Theorem 9: The inverse homomorphism of regular language is regular.

Proof : Let Σ^* → Γ^* is homomorphism.

The Σ is the input set and Γ be the substitution symbols used by homomorphic function.

Let, L be the regular language where L ϵ Σ, then h(L) be homomorphic language. The inverse homomorphic language can be represented as h^-1(L)

Let,

h^-1(L) = {w | wϵL}

If L is regular then h(L) is also regular because regular language is closed under homomorphism. That if there exist a FA M = (Q, ϵ, δ, q₀, F) which accepts L then h(L) must also be accepted by FA M. For complement of L i.e. language L' the inverse homomorphic language is h^-1(L). Let M' be the FA in which all the final states of M become non-final states and all the non-final states of M become the final states. Clearly the language L' can be accepted by M' Hence h^-1(L) must also be accepted by FA M'.

For example - Let L = (010)^* be a regular language. And L = {010, 010010, ...} Let h(0) = a and h(1) = bb be homomorphic function. Then

h(L) = (abba)^*

This L can be represented by following DFA.

Thus there exists a FA which accepts h^-1(1). This shows that, inverse homomorphism of regular language is regular.

Review Questions

1. Show that regular languages are closed under intersection and reversal. AU: Dec.-07, 08, Marks 8

2. Prove that regular sets are closed under substitution. AU: Dec.-10, Marks 6

3. State and prove using an example, the properties of regular language. AU: May-10, Marks 7

4. Prove any two closure properties of regular languages. AU: Dec.-12, Marks 6

5. Discuss in detail about the closure properties of regular languages. AU: May-13, Dec.-13, Marks 8; Dec.-17, Marks 13