If 𝐿 is a regular language over Σ = {𝑎, 𝑏}, which one of the following…

Final answer: The language of the form w w^R (where w ranges over L) is not necessarily regular; the other three constructions are always regular when L is regular.

• L·L^R: Reversal preserves regularity, so L^R is regular. Concatenation of two regular languages is regular. Therefore L·L^R is regular for any regular L.

• {ww^R | w in L}: This need not be regular. Here is a concrete counterexample and a short pumping-lemma argument.

  1. Take L = a* b (which is regular). Then any w in L has the form a^n b, so w w^R = a^n b b a^n.

  2. The resulting language is { a^n b b a^n | n ≥ 0 }, which requires matching the number of a's before and after the central bb and is not regular.

  3. Pumping-lemma sketch: assume the language were regular with pumping length p. Choose s = a^p b b a^p. Any decomposition s = xyz with |xy| ≤ p and |y| ≥ 1 forces y to consist only of a's from the left block. Pumping y out (taking i = 0) yields fewer a's on the left than on the right, so the pumped string cannot be of the form a^n b b a^n. This contradicts the pumping lemma, so the language is not regular.

• Prefix(L): The set of prefixes of a regular language is regular. Given a DFA for L, mark as accepting every state from which some final state is reachable; the modified automaton accepts exactly the prefixes of L.

• Suffix(L): The set of suffixes of L is regular. Suffix(L) = { y | exists x with x y in L } is the right quotient of L by Σ*, and regular languages are closed under right quotients by regular languages. Constructively, from a DFA for L you can build an NFA that treats any state reachable from the start as a possible initial state; this NFA accepts exactly the suffixes.