The GATE Grind

GATE 2020 CS – Question 42

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

Consider the following languages.

$L_1=\{wxyx\mid w,x,y\in(0+1)^+\}$

$L_2=\{xy\mid x,y\in(a+b)^*, |x|=|y|, x\ne y\}$

Which one of the following is TRUE?

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

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $L_1$ is regular and $L_2$ is context-free.

Explanation

$L_1$ is regular: any string with $|w|\ge1$, $|y|\ge1$ and a repeated non-empty $x$ reduces to a simple pattern such as $(0+1)^+ (0+1)(0+1)^+ (0+1)$ with matching symbol, which an NFA can check. $L_2$ is context-free: a string of length $2n$ has $x\ne y$ iff some position $i$ differs between the halves, which a PDA can check using equal-length offsets.