GATE 2022 CS – Question 47
Consider the following languages:
$L_1=\{a^nwa^n\mid w\in\{a,b\}^*\}$
$L_2=\{wxw^R\mid w,x\in\{a,b\}^*,|w|,|x|>0\}$
Note that $w^R$ is the reversal of the string $w$. Which of the following is/are TRUE?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $L_1$ and $L_2$ are regular.; (B) $L_1$ and $L_2$ are context-free.; (C) $L_1$ is regular and $L_2$ is context-free.
Explanation
**$L_1=\{a^nwa^n\mid w\in\{a,b\}^*\}$.** Taking $n=0$ gives $L_1\supseteq\{w\}$ for every $w\in\{a,b\}^*$. So $L_1=\{a,b\}^*$, which is regular.
**$L_2=\{wxw^R\mid |w|,|x|>0\}$.** A string $s$ of length $\ge3$ is in $L_2$ iff its first and last symbols are equal: if they are equal ($=c$), take $w=c$, $w^R=c$ and $x$ the (non-empty) middle part. Conversely, a string $wxw^R$ starts with the first symbol of $w$ and ends with the same symbol. So $L_2=\{c\,(a+b)^+\,c\}$ = $a(a+b)^+a+b(a+b)^+b$, which is regular.
Both are regular, hence also context-free. True statements: A, B, C (D is false).
More Regular and Context-Free Languages, Pumping Lemma questions
- GATE 2022 CS Q48
- GATE 2021 CS (CS1) Q11
- GATE 2020 CS Q18
- GATE 2020 CS Q20
- GATE 2020 CS Q42
- GATE 2019 CS Q17
All Regular and Context-Free Languages, Pumping Lemma questions →