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

Taking n=0 gives $L_1=\{a,b\}^*$, which is regular. $L_2$ is all strings of length ≥3 whose first and last symbols are equal, which is also regular. Hence both are regular, hence context-free, so A, B and C hold and D is false.