GATE 2022 CS – Question 48
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?
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=\{ww\}$ is **not** context-free, and its **complement** is context-free.
- $L_2=\{a^nb^nc^m\}$ and $L_3=\{a^mb^nc^n\}$ are deterministic context-free.
- $L_2\cap L_3=\{a^nb^nc^n\}$ is **not** context-free.
We want the **false** statements:
- (A) "$L_1$ is not CF but $L_2$ and $L_3$ are DCFL." True, so not asked.
- (B) "Neither $L_1$ nor $L_2$ is CF." False, since $L_2$ is CF.
- (C) "$L_2,L_3$ and $L_2\cap L_3$ all CF." False, since the intersection $\{a^nb^nc^n\}$ is not CF.
- (D) "Neither $L_1$ nor its complement is CF." False, since the complement of $\{ww\}$ is CF.
Answer: B, C, D.
More Regular and Context-Free Languages, Pumping Lemma questions
- GATE 2021 CS (CS1) Q11
- GATE 2020 CS Q18
- GATE 2020 CS Q20
- GATE 2020 CS Q42
- GATE 2019 CS Q17
- GATE 2019 CS Q25
All Regular and Context-Free Languages, Pumping Lemma questions →