GATE 2020 CS Q.32: solution and answer

GATE 2020 · CSQ.32 · 2 marks · MCQ

Consider the following languages.
$L_{1} = {w x y x ∣ w, x, y \in (0 + 1)^{+}}$
$L_{2} = {x y ∣ x, y \in (a + b)^{*}, ∣ x ∣ = ∣ y ∣, x \neq = y}$
Which one of the following is TRUE?

(A)
$L_{1}$ is regular and $L_{2}$ is context-free.
(B)
$L_{1}$ is context-free but not regular and $L_{2}$ is context-free.
(C)
Neither $L_{1}$ nor $L_{2}$ is context-free.
(D)
$L_{1}$ is context-free but $L_{2}$ is not context-free.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Option (A): $L_{1}$ is regular and $L_{2}$ is context-free.

Official answer: ASource: Official answer key, GATE 2020 CS (IIT Delhi)

$L_{1}$ is regular. Every string of $L_{1}$ can be rewritten with a one-symbol $x$ . Write a member as $w x y x$ with $x = x_{1} \dots x_{k}$ and let $a = x_{k}$ . Then the string is $(w x_{1} \dots x_{k - 1}) a (y x_{1} \dots x_{k - 1}) a$ . The first and third blocks are nonempty, so it has the form $w^{'} a y^{'} a$ with $w^{'}, y^{'}$ nonempty. Conversely, a string of that form is in $L_{1}$ by taking $x = a$ . So $L_{1} = {w a y a ∣ w, y \in (0 + 1)^{+}, a \in {0, 1}}$ .
A string of length $n$ is in $L_{1}$ exactly when its last symbol $a$ also occurs at some position $p$ with $2 \leq p \leq n - 2$ . Position $p \geq 2$ leaves room for a nonempty $w$ , and $p \leq n - 2$ leaves room for a nonempty $y$ before the final $a$ .
Hence $L_{1} = (0 + 1)^{+} 0 (0 + 1)^{+} 0 + (0 + 1)^{+} 1 (0 + 1)^{+} 1$ . This is a regular expression, so $L_{1}$ is regular, and therefore also context-free.
$L_{2}$ is context-free. A string $z = x y$ with $∣ x ∣ = ∣ y ∣ = n$ is in $L_{2}$ exactly when $z_{p} \neq = z_{p + n}$ for some position $p \leq n$ , so $z$ has even length $2 n$ . Take the grammar $S \to A B ∣ B A$ , $A \to X A X ∣ a$ , $B \to X B X ∣ b$ , $X \to a ∣ b$ . Here $A$ generates exactly the odd-length strings over ${a, b}$ whose middle symbol is $a$ , and $B$ those whose middle symbol is $b$ .
Soundness: let $A$ produce a string of length $2 i + 1$ and $B$ one of length $2 j + 1$ . Then $A B$ has length $2 n$ with $n = i + j + 1$ . The $a$ is at position $i + 1$ and the $b$ is at position $(2 i + 1) + (j + 1) = 2 i + j + 2$ . These are exactly $n$ apart, so the two halves differ at position $i + 1$ . The rule $B A$ is the same with the roles of $a$ and $b$ swapped.
Completeness: if $z$ has length $2 n$ with $z_{p} \neq = z_{p + n}$ and $z_{p} = a$ , split $z$ as $z [1..2 p - 1]$ followed by $z [2 p ..2 n]$ . The first part has odd length and middle symbol $z_{p} = a$ , so $A$ derives it. The second part has length $2 n - 2 p + 1$ and its middle symbol is at position $p + n$ , which is $b$ , so $B$ derives it. If instead $z_{p} = b$ and $z_{p + n} = a$ , the same split works with $B A$ . So the grammar generates exactly $L_{2}$ , and $L_{2}$ is context-free.
Therefore $L_{1}$ is regular and $L_{2}$ is context-free, which is option (A). Options (B) and (D) are false because $L_{1}$ is regular (not 'not regular'), and (D) also because $L_{2}$ is context-free. Option (C) is false because both languages are context-free.

KEY IDEA

The word $w x y x$ with long $x$ collapses to $w a y a$ with a single symbol $a$ , so $L_{1}$ is regular. The set of even-length strings whose halves differ is context-free: guess one mismatch pair, which sits exactly half the length apart, using two odd-length palindrome-style blocks with centres $a$ and $b$ .

WATCH OUT FOR

Treating $L_{1}$ as a 'copy language' that needs memory of $x$ and so is not regular, or thinking $L_{2}$ (with $x \neq = y$ ) is not context-free because ${xx}$ is not. The complement of ${xx}$ is context-free because it only needs to remember one mismatch position.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 8 Context-free languages questions, with notes

GATE 2020 CS Q.32: solution and answer

Answer and solution

More Context-free languages questions