The GATE Grind

GATE 2022 CS – Question 48

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 2 marks · Multiple select

Consider the following languages:
$L_1=\{ww\mid w\in\{a,b\}^*\}$
$L_2=\{a^nb^nc^m\mid m,n\ge0\}$
$L_3=\{a^mb^nc^n\mid m,n\ge0\}$
Which of the following statements is/are FALSE?

  1. $L_1$ is not context-free but $L_2$ and $L_3$ are deterministic context-free.
  2. Neither $L_1$ nor $L_2$ is context-free.
  3. $L_2$, $L_3$ and $L_2\cap L_3$ all are context-free.
  4. Neither $L_1$ nor its complement is context-free.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) Neither $L_1$ nor $L_2$ is context-free.; (C) $L_2$, $L_3$ and $L_2\cap L_3$ all are context-free.; (D) Neither $L_1$ nor its complement is context-free.

Explanation

$L_1$ is not CFL, but $L_2$ and $L_3$ are DCFLs, so A is true and B is false. $L_2\cap L_3=\{a^nb^nc^n\}$ is not CFL, so C is false. The complement of $\{ww\}$ is context-free, so D is false.