edited by
15,437 views
38 votes
38 votes

Consider the following languages.

$L_1 = \left \{ 0^p1^q0^r \mid p,q,r \geq 0 \right \}$

$L_2 = \left \{ 0^p1^q0^r \mid p,q,r \geq 0, p\neq r \right \}$

Which one of the following statements is FALSE?

  1. $L_2$ is context-free.
  2. $L_1\cap L_2$ is context-free.
  3. Complement of $L_2$ is recursive.
  4. Complement of $L_1$ is context-free but not regular.
edited by

2 Answers

Best answer
57 votes
57 votes

$L_1$ is regular and hence context-free also. Regular expression for $L_1 $is $0^*1^*0^*$. So, (D) is the false choice. 

$L_2$ is context-free but not regular.  We need a stack to count if the number of $0$'s before and after the $1$ ($1$ may be absent also) are not same. So, $L_1 \cap L_2$ is context-free as regular $\cap$ context-free is context-free. $\rightarrow$ (B) is true.

Complement of $L_2$ is recursive as context-free complement is always recursive (actually even context-sensitive).

 
edited by
13 votes
13 votes

for $L_1$ we can see that $p, q, r$ are independent of each other $\therefore$ the language is Regular.

for $L_2$ we can see that only one comparison is there which is between $p$ and $r$. variable $q$ is independent of the two. Hence it can be seen that it is DCFL.

$A$ : saying $L_2$ is CFL is True.

$B$ : intersection of a CFL with Regular is closed $\therefore$ this option is True.

$C$ : the complement of any CFL is Recursive, since recursive languages are closed under complement and all CFLs are R. $\therefore$ this option is True

$D$ : Regular languages are closed under complement Hence, this option is FALSE.

answer = option D

Answer:

Related questions

44 votes
44 votes
2 answers
1