## Idntify Class Language

 Question 1
Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?
 A L1 ∩ L2 is a deterministic CFL B L3 ∩ L1 is recursive C L1 ∪ L2 is context free D L1 ∩ L2 ∩ L3 is recursively enumerable
Theory of Computation        Idntify Class Language       Gate-2006
Question 1 Explanation:
Option A is true, as by closure property (R is a regular language and L is any language)
L ∩ R = L ( i.e. L Intersection R is same type as L )
So L1 ∩ L2 is a deterministic CFL.
Option B is false, as L3 is recursive enumerable but not recursive, so intersection with L1 must be recursive enumerable, but may or may not be recursive.
Option C is true, as by closure property (R is a regular language and L is any language)
L U R = L ( i.e. L UNION R is same type as L )
So, L1 ∪ L2 is deterministic context free, hence it is also context free.
Option D is true, as L1 ∩ L2 is DCFL and DCFL ∩ L3 is equivalent to DCFL ∩ Recursive enumerable.
As every DCFL is recursive enumerable, so it is equivalent to Recursive enumerable ∩ Recursive enumerable. And recursive enumerable are closed under INTERSECTION so it will be recursive enumerable.
There is 1 question to complete.