GATE 2022 CS Q.47: solution and answer

GATE 2022 · CSQ.47 · 2 marks · MSQ

Consider the following languages:

$L_{1} = {a^{n} w a^{n} ∣ w \in {a, b}^{*}}$

$L_{2} = {w x w^{R} ∣ w, x \in {a, b}^{*}, ∣ w ∣, ∣ x ∣ > 0}$

Note that $w^{R}$ is the reversal of the string $w$ . Which of the following is/are TRUE?

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

A, B and C are true; D is false.

Official answer: A, B, CSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

$L_{1}$ : here $w \in {a, b}^{*}$ is arbitrary (it may be empty). Taking $n = 1$ gives every string $a w a$ . A larger $n$ gives nothing new, because $a^{n} w a^{n} = a (a^{n - 1} w a^{n - 1}) a$ already has the form $a w^{'} a$ . Hence $L_{1} = a (a + b)^{*} a$ , the strings of length at least 2 that start and end with $a$ . If $n = 0$ is also allowed, $L_{1} = {a, b}^{*}$ . Either way $L_{1}$ is regular.
$L_{2}$ : take $∣ w ∣ = 1$ , say $w = c \in {a, b}$ . Then $w x w^{R} = c x c$ with $x$ non-empty, which gives every string of length at least 3 that starts and ends with the same symbol.
A longer $w$ gives nothing new. The string $w x w^{R}$ starts with the first symbol of $w$ and ends with that same symbol. Its length is at least 3 because $∣ w ∣, ∣ x ∣ > 0$ . Writing $c$ for the first symbol, the string is $c y c$ with $y$ non-empty. So $L_{2} = a (a + b)^{+} a + b (a + b)^{+} b$ , which is regular.
So both $L_{1}$ and $L_{2}$ are regular. The reversal in $L_{2}$ looks as if it needs a stack. But the free middle part $x$ means a finite automaton only has to compare the first and last symbols.
Every regular language is context-free, so $L_{1}$ and $L_{2}$ are both context-free.
Check the options. (A) true. (B) true, since regular implies context-free. (C) true, since $L_{1}$ is regular and $L_{2}$ , being regular, is context-free. (D) false, because neither language is non-regular.

KEY IDEA

The free middle part ( $w$ in $L_{1}$ , $x$ in $L_{2}$ ) absorbs everything except the first and last symbols. So both languages reduce to a check on the end symbols, and both are regular. Every regular language is context-free.

WATCH OUT FOR

Reading $w x w^{R}$ as a palindrome-like language that needs a stack and so is non-regular. The non-empty free $x$ between $w$ and $w^{R}$ means only the first and last symbols matter, so this is not the language ${w w^{R}}$ .

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

GATE 2022 CS Q.47: solution and answer

Answer and solution

More Context-free languages questions