Consider the following languages: L_1 = \ww w ∈ \a, b\^*\ L_2 = \a^n b^n c^m m, n ≥ 0\ L_3 = \a^m b^n c^n m, n ≥ 0\ Which of the following statements is/are FALSE?

Neither L_1 nor L_2 is context-free.

L_2, L_3 and L_2 L_3 all are context-free.

Neither L_1 nor its complement is context-free.

L_1 is not context-free but L_2 and L_3 are deterministic context-free.

Neither L_1 nor L_2 is context-free.

L_2, L_3 and L_2 L_3 all are context-free.

Neither L_1 nor its complement is context-free.

GATE CSE 2022 Q48: False statements about ww, aⁿbⁿcᵐ and aᵐbⁿcⁿ

Consider the following languages:

$L_1 = \{ww \mid w \in \{a, b\}^*\}$

$L_2 = \{a^n b^n c^m \mid m, n \ge 0\}$

$L_3 = \{a^m b^n c^n \mid m, n \ge 0\}$

Which of the following statements is/are FALSE?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: B, C, D (official GATE 2022 final answer key)

Concept used: $L_2 \cap L_3 = \{a^n b^n c^n\}$ is not context-free; the complement of $\{ww\}$ is context-free.

First step: Classify each language first: $L_2$ and $L_3$ need one counter each (DCFL), $L_1$ is not CFL.

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2022 CS question paper and final answer key, organised by IIT Kharagpur. Question paper · Answer key