If L is a regular language over Sigma = {a, b}, which one of the following languages is NOT regular? A. L^R = {xy | x in L, y^R in L} B. {ww^R | w in L} C. Prefix(L) = {x in Sigma* | there exists y in Sigma* such that xy in L} D. Suffix(L) = {y in Sigma* | there exists x in Sigma* such that xy in L}
GATE 2019 · Theory of Computation · Regular Language · medium
Answer: Option B: {ww^R | w in L} is NOT regular in general, even when L is regular.
- Check Option A: L^R = {xy | x in L, y^R in L}: The set {xy | x in L, y^R in L} equals L concatenated with (L^R)^R = L. Wait — y^R in L means y in L^R. So the set is {xy | x in L, y in L^R} = L . L^R. Since L is regular, L^R is regular, and the concatenation of two regular languages is regular. So Option A is regular.
- Check Option B: {ww^R | w in L}: Consider L = (a+b)*. Then {ww^R | w in L} = the set of all even-length palindromes over {a,b}. This language is NOT regular (it requires a stack to match characters). More generally, even if L is restricted, the language {ww^R | w in L} requires a non-regular matching of w with its mirror image. This language is context-free but not necessarily regular.
- Check Options C and D: Prefix and Suffix: Prefix(L) and Suffix(L) are both regular when L is regular. These are standard closure results. The DFA for L can be easily modified to accept any string that is a prefix (or suffix) of some accepted string.