GATE 2020 CS – Question 42
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?
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
- GATE 2019 CS Q17
- GATE 2019 CS Q25
- GATE 2017 CS (CS1) Q48
- GATE 2014 CS (CS1) Q25
- GATE 2014 CS (CS2) Q25
- GATE 2014 CS (CS2) Q46
All Regular and Context-Free Languages, Pumping Lemma questions →