Consider the following languages: L_1 = \a^n w a^n w ∈ \a, b\^*\ L_2 = \w x w^R w, x ∈ \a, b\^*, |w|, |x| > 0\ Note that w^R is the reversal of the string w. Which of the following is/are TRUE?

L_1 is regular and L_2 is context-free.

L_1 and L_2 are context-free but not regular.

GATE CSE 2022 Q47: Classify a^n w a^n and w x w^R

Consider the following languages:

$L_1 = \{a^n w a^n \mid w \in \{a, b\}^*\}$

$L_2 = \{w x w^R \mid 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?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: A, B, C (official GATE 2022 final answer key)

Concept used: When the middle part is unrestricted, it can absorb almost everything, so these languages collapse to simple regular ones.

First step: In $L_2$ take $|w| = 1$ : the language is all strings of length at least 3 whose first and last symbols are equal.

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2022 CS question paper and final answer key, organised by IIT Kharagpur. Question paper · Answer key