The GATE Grind

GATE 2019 CS – Question 17

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 1 mark · Multiple choice

If $L$ is a regular language over $\Sigma=\lbrace a,b\rbrace $, which one of the following languages is NOT regular?

  1. $L\cdot L^R=\lbrace xy\mid x\in L,\ y^R\in L\rbrace $
  2. $\lbrace ww^R\mid w\in L\rbrace $
  3. Prefix$(L)=\lbrace x\in\Sigma^*\mid\exists y\in\Sigma^*$ such that $xy\in L\rbrace $
  4. Suffix$(L)=\lbrace y\in\Sigma^*\mid\exists x\in\Sigma^*$ such that $xy\in L\rbrace $

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\lbrace ww^R\mid w\in L\rbrace $

Explanation

Regular languages are closed under reversal, concatenation, prefix and suffix, so A, C and D are regular. But $\lbrace ww^R\mid w\in L\rbrace $ need not be: for $L=a^*b$ we get $\lbrace a^nbba^n\rbrace $, which is not regular.