Consider the following languages. L1 = \wxyx w, x, y (0 + 1)+\ L2 = \xy x, y (a + b)*, |x| = |y|, x y\ Which one of the following is TRUE? A) L1 is regular and L2 is context-free. B) L1 is context-free but not regular and L2 is context-free. C) Neither L1 nor L2 is context-free.

Official answer: A) L1 is regular and L2 is context-free.. Explanation: ### Analysis of L1: L1 = \wxyx w, x, y (0 + 1)+\ Notice that if x is chosen to be a single character c \0, 1\, the string has the form w c y c where w, y (0+1)+. Any string in L1 has x ending in either 0 or 1. Let x = x'c with c \0, 1\, then: wxyx = w(x'c)y(x'c) = (wx')c(yx')c Since w, y (0+1)+, wx' (0+1)+ and yx' (0+1)+. Thus, any string in L1 matches the regular expression: (0+1)+ 0 (0+1)+ 0 + (0+1)+ 1 (0+1)+ 1 Conversely, any string matching this regular expression belongs to L1 by setting x = c. Because L1 can be expressed by a regular expression, L1 is regular. ### Analysis of L2: L2 = \xy x, y (a + b)*, |x| = |y|, x y\ L2 consists of all even-length strings where the first half is not equal to the second half. x y implies there is some position i (1 i |x|) such that the i-th character of x differs from the i-th character of y. This can be generated by a Context-Free Grammar (CFG): - S AB BA - A CAC a - B CBC b - C a b Here, A generates strings of odd length with 'a' in the middle, and B generates strings of odd length with 'b' in the middle. The concatenation AB or BA generates strings of even length 2n where the i-th character from the start and the (n+i)-th character from the start differ. Since a CFG exists, L2 is context-free (non-deterministic CFL, not regular). Therefore, L1 is regular and L2 is context-free, making A the correct option. *(Note: Option D was printed on the succeeding page and is omitted as per partial extraction rules.)*

A) L1 is regular and L2 is context-free.

B) L1 is context-free but not regular and L2 is context-free.

C) Neither L1 nor L2 is context-free.

Theory of Computation · Regular and Context-Free Languages

Official IIT answer key · IIT Delhi · Audited Aug 2026

Take topic test

GATE CSE 2020 Q32 · MCQ · 2 marks

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 \neq y\}$ Which one of the following is TRUE?

Select an option to check

Key concept

Regular and Context-Free Languages

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Regular and Context-Free Languages

GATE consistently tests Regular and Context-Free Languages by evaluating closure properties, set-theoretic algebraic manipulations, and language classification (Regular vs. DCFL vs. CFL vs. Non-CFL). Questions heavily emphasize edge-case reasoning with universal ( *) and empty ( ) languages, as well as structural recognizability via finite automata versus deterministic/non-deterministic pushdown automata. Recent exams (2021–2026) strongly favor Multi-Select Questions (MSQ) testing multiple interdependent closure and membership assertions simultaneously.

Full Regular and Context-Free Languages guide →

More on Regular and Context-Free Languages

All 21 questions on Regular and Context-Free Languages →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Theory of Computation · Regular and Context-Free Languages

Official IIT answer key · IIT Delhi · Audited Aug 2026

Take topic test

GATE CSE 2020 Q32 · MCQ · 2 marks

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 \neq y\}$ Which one of the following is TRUE?

Select an option to check

Key concept

Regular and Context-Free Languages

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Regular and Context-Free Languages

Full Regular and Context-Free Languages guide →

More on Regular and Context-Free Languages

All 21 questions on Regular and Context-Free Languages →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

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 \neq y\}$ Which one of the following is TRUE?

Step-by-step verified solution

Check you can still solve Regular and Context-Free Languages under a clock

More from GATE CSE 2020

More on Regular and Context-Free Languages

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 \neq y\}$ Which one of the following is TRUE?

Step-by-step verified solution

Check you can still solve Regular and Context-Free Languages under a clock

More from GATE CSE 2020

More on Regular and Context-Free Languages

Step-by-step verified solution

Check you can still solve Regular and Context-Free Languages under a clock

More from GATE CSE 2020

More on Regular and Context-Free Languages

Share this solution

Step-by-step verified solution

Check you can still solve Regular and Context-Free Languages under a clock

More from GATE CSE 2020

More on Regular and Context-Free Languages

Share this solution