Question

Consider the following languages.
$L_1=${$a^i{b}^j{c}^k|i=j,k\ge 1$}
$L_2=${$a^i{b}^j|j=2i,i\ge 0$}
Which of the following is true?

Answer 1

L1 is CFL [push a's onto stack, and pop a with each b]
L2 is CFL [push b's onto stack and pop b with each c]. So, option (a) is false.
In L1, every string has atleast one "c".
In L2, every string has no "c".
So, L1 $\cap$ L2= $\varphi$. So option (b) is true.
Union of two CFLs is a CFL and so option (c) is false.
L2 is DCFL and hence acceptable by a DPDA.
So, option (d) is false.