Closure-Property

Question 1
Suppose that L1is a regular language and L2is a context free language. Which one of the following languages is NOT necessarily context free?
A
L1. L2
B
L1 ∪ L2
C
L1 ∩ L2
D
L1 − L2
Question 1 Explanation: 

L1. L2 =>  regular . CFL  == CFL. CFL  (as every regular is CFL so we can assume regular as CFL)

Since CFL is closed under concatenation so 

CFL. CFL= CFL  

Hence

Regular . CFL = CFL is true

 

L1 ∪ L2 => Regular ∪ CFL = CFL 

Regular ∪ CFL = CFL ∪ CFL  (as every regular is CFL so we can assume regular as CFL)

 

Since CFL is closed under union 

Hence Regular ∪ CFL = CFL   is true

 

L1 ∩ L2 => Regular ∩ CFL = CFL 

Regular languages are closed under intersection with any language

I.e,

Regular ∩ L = L  (where L is any language such as CFL, CSL etc)

 

Hence Regular ∩ CFL = CFL  is true

 

Please note this is a special property of regular languages so we will not upgrade regular into CFL (as we did in S1 and S2). We can directly use these closure properties.

 

L1 − L2 => Regular − CFL = CFL 

=> Regular − CFL = regular ∩ CFL (complement)

Since CFL is not closed under complement so complement of CFL may or may not be CFL

 

Hence Regular − CFL need not be CFL

 

For ex:

R= (a+b+c)*  and L= {am bn ck | m ≠ n or n ≠ k} which is CFL.

 

The complement of L = {an bn cn | n>0} which is CSL but not CFL.

 

So 

R L = (a+b+c)* {am bn ck | m ≠ n or n ≠ k}

 

=> (a+b+c)* ∩  L (complement) 

=> (a+b+c)* ∩  {an bn cn | n>0}

=> {an bn cn | n>0}

 

Which is CSL. Hence Regular − CFL need not be CFL.

Question 2

The set of all recursively enumerable languages is

A
closed under complementation.
B
closed under intersection.
C
a subset of the set of all recursive languages.
D
an uncountable set.
Question 2 Explanation: 
Recursive enumerable languages are closed under intersection.
Recursive enumerable languages are not closed under Complementation.
Recursive enumerable languages are a countable set, as every recursive enumerable language has a corresponding Turing Machine and set of all Turing Machine is countable.
Recursive languages are subset of recursive enumerable languages.
There are 2 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access