Closure Properties of Context Free Languages

In this class, We discuss the Closure Properties of Context-Free Languages.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of context-free grammar and push-down automata. Click Here.

1) Union:

First, we understand what closure property means.

Context-free languages are closed under union.

Let’sLet’s take two context-free languages, L1 and L2.

Suppose L1 ∪ L2 is also a context-free language. Then, we say context-free languages are closed under union.

Proof: Take L1 and L2 languages.

L1 ∪ L2 is given as { Strings from L1 or Strings from L2}

Take any string from language L1 or take any string from language L2.

L1: S1 – aA

A – b

L2: S2 – bBa

B – aB | ε

The below CFG shows the language L1 U L2.

S – S1 | S2

S1 – aA

A – b

S2 – bBa

B – aB | ε

By adding an extra production S – S1 | S2, we write CFG for language L1 U L2.

2) Concatenation:

Context-free languages are closed under concatenation.

Take two context-free languages, L1 and L2.

L1.L2 is given as {String from L1 followed by String from L2}

By adding extra production S – S1S2, we get the context-free grammar for the language L1.L1

3) Kleen Closure:

Context-free languages are closed under Kleen Closure.

Kleen closure means star operator.

Take a Context-free language L1.

L1: S1 – aA

A – b

Star operator means we take a string from the language L1 and repeat any number of times or epsilon.

We add an extra production to repeat the language L1.

S – S1S | ε

The production S identifies strings from S1 and again repeats by calling S or epsilon.

4) Intersection:

Context free languages are not closed under intersection.

Proof: take language L1 = {0^n1^n2^m where n,m >=0}

language L2 = {0^n1^m2^m where n,m >=0}

The above two languages are context-free languages.

L1 ∩ L2 should take common strings.

The strings in L1 ∩ L2 are { 0^k1^k2^k where K >=0}

The language L1 ∩ L2 is not a context-free grammar.

5) Complement:

Context-free languages are not closed under complement.

L1 ∩ L2 can be written (L1′ U L2′)’ where ” ‘ “is a compliment.

If we assume the complement is closed, the intersection should be closed, which is a contradiction.

6) Difference:

Context-free languages are not closed under difference

The intersection of two languages can be written as L1 ∩ L2 = L1 – (L1 – L2).

If we assume the difference is closed, the intersection should be closed, which is contradictory.

7) Reverse:

Context-Free Languages are closed under Reverse.

Take a context free language L1 = {0ⁿ1ⁿ where n > 0}

The CFG for the language L1 is S – 0S1 | 01

The CFG for Reverse of the given language is given by reversing the productions.

The CFG for the Reverse of L1 is S – 1S0 | 10

8) Homomorphism:

Context-Free Languages are closed under homomorphism.

Take a language L1 is S – 0S1 | 01

Given h(0) = ab and h(1) = ε

The given input string is substituted with ab in place of zero.

The given input string is substituted with epsilon in place of one.

The language obtained after substitution of homomorphism values. we call Lh.

We use the substitution in the given CFG to obtain the CFG for Lh.

S – abS |ab