The GATE Grind

GATE 2022 CS – Question 47

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

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?

  1. $L_1$ and $L_2$ are regular.
  2. $L_1$ and $L_2$ are context-free.
  3. $L_1$ is regular and $L_2$ is context-free.
  4. $L_1$ and $L_2$ are context-free but not regular.

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

All Regular and Context-Free Languages, Pumping Lemma questions →