Theory of Computation
Finite Automata & Regular Languages
GATE 2019
Hard
If L is a regular language over Σ={a,b}, which one of the following languages is NOT regular?
- AL·L^R = {xy | x∈L, y^R∈L}
- {ww^R | w∈L}
- CPrefix(L) = {x∈Σ* | ∃y∈Σ* such that xy∈L}
- DSuffix(L) = {y∈Σ* | ∃x∈Σ* such that xy∈L}
Explanation
Regular languages are closed under reversal, concatenation, and taking Prefix/Suffix closures — so A, C, and D are all regular. But {ww^R | w∈L} requires remembering an unbounded amount of the exact content of w to verify the second half is its mirror image — this construction is generally NOT regular even when L itself is regular (it's essentially embedding an unbounded exact-match requirement, like the classic non-regular {ww} pattern).
Source: GATE CS 2019 (Set-2) (2019)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.