Let L1 be a regular language, L2 be a deterministic context-free language and…
2006
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
Attempted by 8 students.
Show answer & explanation
Correct answer: B
L1 is regular and L3 is recursively enumerable but not recursive. The intersection of a regular language with a recursively enumerable language remains recursively enumerable, as regular languages are closed under intersection. However, L3 ∩ L1 cannot be recursive because L3 itself is not recursive, and closure under intersection does not make it recursive. Therefore, statement B claiming L3 ∩ L1 is recursive is false. The other options are true: regular ∩ deterministic CFL remains deterministic CFL, union of regular and DCFL is context-free, and intersection of all three languages preserves recursive enumerability.