12,427 views
57 votes
57 votes

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?

  1. $L_1 \cap L_2$  is a deterministic CFL
  2. $L_3 \cap L_1$  is recursive
  3. $L_1 \cup L_2$  is context free
  4. $L_1 \cap L_2 \cap L_3$  is recursively enumerable

2 Answers

Best answer
66 votes
66 votes
  1. True : DCFL are closed under Intersection with Regular Languages
  2. False : $L_1$ is recursive hence also decidable, $L_3$ is RE but not Recursive hence it is undecidable. Intersection of Recursive language and Recursive Enumerable language is Recursive Enumerable language.
  3. True : $L_1$ is regular hence also CFL and every DCFL is also CFL and All CFL are closed under Union.
  4. True : $L_1$ is regular hence also RE; $L_2$ is DCFL hence also RE; RE languages are closed under Intersection
edited by
5 votes
5 votes
L1∩L2 is a deterministic CFL because intersection of any lang. with regular is closed.

L3∩L1 is recursive is False because it should be RE {recursive enumerable not recursive}

L1∪L2 is context free is true, because every DCFL is CFL.

L1∩L2∩L3 is recursively enumerable is true.
Answer:

Related questions

93 votes
93 votes
8 answers
2
Rucha Shelke asked Sep 22, 2014
33,981 views
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is:$3$$5$$8$$9$