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=\{wxyx\mid w,x,y\in(0+1)^+\}$ is regular.**
Let the last symbol be $c$. If the string is in $L_1$, its last symbol is the last symbol of the final $x$, and that symbol also occurs inside the earlier copy of $x$, at a position that is neither first nor adjacent to the end, so the string has the form $w\,\ldots c\,y\,c$ with $c$ occurring again in the middle. Conversely, if the last symbol $c$ occurs at some position $i$ with $2\le i\le n-2$, take $x=c$ (a single symbol), $w$ the part before position $i$, and $y$ the part between position $i$ and the last symbol. So $L_1$ is the set of strings whose last symbol also appears among positions $2,\dots,n-2$, which a finite automaton can check. Regular.

**$L_2=\{xy\mid |x|=|y|,\ x\ne y\}$ is context-free.**
A string of length $2n$ is in $L_2$ iff some position $i$ has a different symbol in the first half than in the second half. Look at the string as: (stuff of length $i-1$), the symbol $a$, (stuff of length $n-i$), (stuff of length $i-1$), the symbol $b\ne a$, (stuff of length $n-i$). Rearranged, this is
$$\underbrace{\Sigma^{i-1}\,a\,\Sigma^{n-i}\ \Sigma^{i-1}}_{\text{length }n+i-1}\ b\ \Sigma^{n-i},$$
and the language $\{\Sigma^{k}\,a\,\Sigma^{m}\ \Sigma^{k}\,b\,\Sigma^{m}\}$ with $a\ne b$ can be generated by a grammar of the form $S\to AB\mid BA$, $A\to XAX\mid a$, $B\to XBX\mid b$ ($X$ any symbol), because $A$ generates strings of odd length with `a` in the exact middle, and $B$ likewise with `b`. This is the standard context-free grammar for "the two halves differ somewhere".

So $L_1$ is regular and $L_2$ is context-free: option (A).

More Regular and Context-Free Languages, Pumping Lemma questions

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