Let L1 be a regular language, L2 be a deterministic contextfree

Home » Theory of Computation » Theory of computation miscellaneous » Question

Let L₁ be a regular language, L₂ be a deterministic contextfree language and L₃ a recursively enumerable but not recursive language. Which one of the following statements is false?

1. L₁ ∩ L₂ is a deterministic CFL
2. L₂ ∩ L₁ is recursive
3. L₁ ∩ L₂ is context-free
4. L₁ ∩ L₂ ∩ L₃ is recursively enumerable

Correct Option: B

L₁ is regular language
L₂ is CFL.
L₃ is recursively enumerable but not REC.
(a) L₁ ∩ L₂ is CFL is true
(b) L₃ ∩ L₁ is recursive, not necessary so false.
(c) & (d) are also true.