GateAI
Regular and Context-Free Languages

GATE CSE 2019 · Q7

MCQ1 markMedium

Time

If LL is a regular language over Σ={a,b}\Sigma = \{a, b\}, which one of the following languages is NOT regular ?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: B) {wwR w ∈ L}

Regular and Context-Free Languages

Let us analyze the closure properties for each option:

  • Option A: L⋅LRL \cdot L^R: Regular languages are closed under reversal (LRL^R is regular) and concatenation. Thus, L⋅LRL \cdot L^R is always regular.

  • Option B: {wwR∣w∈L}\{ww^R \mid w \in L\}: Here, every word w∈Lw \in L must be concatenated with its specific reverse wRw^R. If L=Σ∗=(a+b)∗L = \Sigma^* = (a+b)^*, then {wwR∣w∈L}={wwR∣w∈{a,b}∗}\{ww^R \mid w \in L\} = \{ww^R \mid w \in \{a,b\}^*\}, which is the classic non-regular language of even-length palindromes (requires an unbounded stack memory to verify). Hence, this language is not necessarily regular.

  • Option C: Prefix(L)\text{Prefix}(L): Regular languages are closed under the prefix operation.

  • Option D: Suffix(L)\text{Suffix}(L): Regular languages are closed under the suffix operation.

Therefore, B is NOT regular.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Regular and Context-Free Languages previous year question is Q7 of the GATE CSE 2019 paper. Find more GATE CSE PYQs on Regular and Context-Free Languages in Theory of Computation, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Regular and Context-Free Languages PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Regular and Context-Free Languages in GATE CSE

Regular and Context-Free Languages has 21 GATE CSE PYQs across 13 papers from 2011 to 2026. 5 of them are 1-mark MCQs like this one, and GATE CSE 2019 has 3.

How GATE tests Regular and Context-Free Languages

More from GATE CSE 2019

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2019 · Q7 · MCQ

If L is a regular language over = {a, b}, which one of the following languages is NOT regular ?

Topic-wise GATE CS PYQs with verified steps

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