## Idntify Class Language

Question 1 |

Let L

_{1}be a regular language, L_{2}be a deterministic context-free language and L_{3}a recursively enumerable, but not recursive, language. Which one of the following statements is false?L _{1} ∩ L_{2} is a deterministic CFL | |

L _{3} ∩ L_{1} is recursive | |

L _{1} ∪ L_{2} is context free | |

L _{1} ∩ L_{2} ∩ L_{3} is recursively enumerable |

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 L

Option B is false, as L

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, L

Option D is true, as L

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.

L ∩ R = L ( i.e. L Intersection R is same type as L )

So L

_{1}∩ L_{2}is a deterministic CFL.Option B is false, as L

_{3}is recursive enumerable but not recursive, so intersection with L_{1}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, L

_{1}∪ L_{2}is deterministic context free, hence it is also context free.Option D is true, as L

_{1}∩ L_{2}is DCFL and DCFL ∩ L_{3}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.