Which of the following languages is regular?

Correct identification: The language {w x w^R | x,w ∈ {0,1}^+} is regular.

Reason (characterization): a string s belongs to {w x w^R | x,w ∈ {0,1}^+} exactly when |s| ≥ 3 and the first and last symbols of s are equal.

• If s = w x w^R, then the last symbol of s is the last symbol of w^R, which equals the first symbol of w, so the first and last symbols of s are equal. Also w and x are nonempty, so |s| ≥ 3.

• Conversely, if s has length at least 3 and its first and last symbols are equal (say both are a), write s = a y a with y nonempty. Take w = a and x = y; then s = w x w^R, so s is in the language.

Regular expression (one convenient description):

(0(0|1)+0) ∪ (1(0|1)+1)

Why the other three languages are not regular:

• {w w^R | w ∈ {0,1}^+} is the set of even-length palindromes and is not regular. Sketch: use the pumping lemma on s = 0^p0^p; any pumping inside the first half destroys the required mirror structure.

• {w w^R x | x,w ∈ {0,1}^+} is not regular. Sketch using closure properties: if this language were regular then taking the right quotient by {0,1}^+ (a regular set) would yield a language that contains {w w^R}, contradicting the non-regularity of {w w^R}. A pumping-lemma proof focusing on the initial mirror block can also be given.

• {x w w^R | x,w ∈ {0,1}^+} is not regular. Similar reasoning applies: if it were regular, left-quotienting by {0,1}^+ or reversing and using closure properties would produce {w w^R}, a non-regular language; or use a pumping-lemma argument on the trailing mirror block.