Let 2 be the same as in Problem 1.33. Consider the top and bottom rows to be strings of 0s and 1s, and let

Let Σ₂ be the same as in Problem 1.33. Consider the top and bottom rows to be strings of 0s and 1s, and let E = {w ∈ Σ^*₂| the bottom row of w is the reverse of the top row of w}. Show that E is not regular.

Problem 1.33.

For any string w = w₁w₂ · · ·w_n, the reverse of w, written w^R, is the string w in reverse order, w_n · · ·w₂w₁. For any language A, let A^R = {w^R| w ∈ A}. Show that if A is regular, so is A^R.