GATE 2022 CS Q.48: solution and answer

GATE 2022 · CSQ.48 · 2 marks · MSQ

Consider the following languages:
$L_{1} = {w w ∣ w \in {a, b}^{*}}$
$L_{2} = {a^{n} b^{n} c^{m} ∣ m, n \geq 0}$
$L_{3} = {a^{m} b^{n} c^{n} ∣ m, n \geq 0}$
Which of the following statements is/are FALSE?

(A)
$L_{1}$ is not context-free but $L_{2}$ and $L_{3}$ are deterministic context-free.
(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.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The false statements are (B), (C) and (D).

Official answer: B, C, DSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

$L_{1} = {w w ∣ w \in {a, b}^{*}}$ is the copy language. It is not context-free (pumping lemma for CFLs, or the standard result). So the first half of (A) is correct.
$L_{2} = {a^{n} b^{n} c^{m} ∣ m, n \geq 0}$ is accepted by a DPDA that pushes a symbol for each $a$ , pops one for each $b$ , then reads any number of $c$ 's and accepts on empty stack. So $L_{2}$ is a deterministic context-free language. A grammar is $S \to X C$ , $X \to a X b ∣ ε$ , $C \to c C ∣ ε$ .
$L_{3} = {a^{m} b^{n} c^{n} ∣ m, n \geq 0}$ is accepted by a DPDA that skips the $a$ 's, pushes for each $b$ and pops for each $c$ . So $L_{3}$ is a DCFL. Hence statement (A) is TRUE.
Statement (B) says $L_{2}$ is not context-free. But $L_{2}$ is context-free by step 2, so (B) is FALSE.
$L_{2} \cap L_{3} = {a^{n} b^{n} c^{n} ∣ n \geq 0}$ , which is not context-free (pumping lemma for CFLs). Statement (C) claims it is context-free, so (C) is FALSE.
The complement of $L_{1}$ is context-free. A string over ${a, b}$ is outside $L_{1}$ if its length is odd, or if its length is $2 n$ and some position $i$ and position $i + n$ hold different symbols. A PDA can guess the position, push a count while reading, and match it against the second half. This gives a CFL. Statement (D) says neither $L_{1}$ nor its complement is context-free, so (D) is FALSE.
The FALSE statements are B, C and D.

KEY IDEA

$L_{1} = {w w}$ is not context-free but its complement is. $a^{n} b^{n} c^{m}$ and $a^{m} b^{n} c^{n}$ are DCFLs, and their intersection $a^{n} b^{n} c^{n}$ is not context-free, so CFLs are not closed under intersection.

WATCH OUT FOR

Assuming that because ${w w}$ is not context-free, its complement cannot be either. The complement is context-free because a PDA can guess one mismatching position. Another slip is treating $L_{2} \cap L_{3}$ as context-free just because $L_{2}$ and $L_{3}$ are.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 8 Context-free languages questions, with notes

GATE 2022 CS Q.48: solution and answer

Answer and solution

More Context-free languages questions