Question

Consider the following languages
$L_1$ ={$0^p{1}^q{0}^r|p,q,r\ge 0$}
$L_2$ ={$0^p{1}^q{0}^r|p,q,r\ge 0,p\ne r$}
Which one of the following statements is FALSE?

• A. $L_1\cap L_2$ is context-free
• B. $L_2$ is context-free
• C. Complement of $L_1$ is context-free but not regular
• D. Complement of $L_2$ is recursive

Answer 1

The correct option is C Complement of $L_1$ is context-free but not regular

$L_1$={$0^p{1}^q{0}^r|p,q,r\ge 0$}:regular language
$L_2$={$0^p{1}^q{0}^r|p,q,r\ge 0,p\ne r$}; CFL
(a) $L_2$ is CFL ; True
(b) $L_1\cap L_2$ is context free : True, becuase CFL is closed on regular intersection.
(c) Complement of $L_2$ is recursive :
${\overline{L}}_2$ =$\overline{CFL}=\overline{CSL}=CSL$
Now, every CSL is REC. So,this statement is true
(d) Complement of $L_1$ is is context free but not regular : false,becuase regular language are closed under complement and so the complement of $L_1$ is regular.