Section Project: Reversed Strings and Palindromes
Definition 9.40.
If \(w\in \Sigma^*\text{,}\) we define \(w^R\in \Sigma^*\) recursively as follows.
\(\lambda^R = \lambda\) and \(a^R = a\) for all \(a\in \Sigma\text{.}\)
If \(w = av\) where \(a\in \Sigma\) and \(v\in \Sigma^*\text{,}\) then \(w^R = v^Ra\text{.}\)
Problem 9.41.
Use Definition 9.40 to compute \(w^R\) if \(w=pots\text{.}\) What is \(w^R\) if \(w = scitamehtametercsid\text{?}\)
Problem 9.42.
Let \(\Sigma =\{a,b\}\text{.}\) List all the strings in the finite language \(L = \{w \in \Sigma^* \mid w = uu^Ru \mbox{ for some } u\in \Sigma \Sigma\}\text{,}\) remembering that \(\Sigma \Sigma\) is the concatenation of \(\Sigma\) with itself.
Problem 9.43.
Let \(\Sigma =\{a,b\}\text{.}\) Describe a method to generate all of the strings in the language \(L = \{w \in \Sigma^* \mid www = uu \mbox{ for some } u \in \Sigma^*\}\text{,}\) and explain why your method is correct.
Problem 9.44.
Let \(\Sigma =\{a,b\}\) and \(L = \{w \in \Sigma^* \mid w^Rw = ww^R\}\text{.}\) Give examples of two strings in \(L\) and two strings not in \(L\text{.}\) Describe the strings of \(L\) in English.
Definition 9.45.
A string \(w \in \Sigma^*\) is a palindrome if \(w^R = w\text{.}\)
For example, A, EYE, NOON, CIVIC and MADAM are all palindromes.
Problem 9.46.
Prove by induction on the length \(u\) of the string \(u\in \Sigma^*\) that, for all \(v\in \Sigma^*\text{,}\) we have \((uv)^R = v^Ru^R\text{.}\)
Problem 9.47.
Let \(u\in \Sigma^*\) and \(b \in \Sigma\text{.}\) Show that \(uu^R\) and \(ubu^R\) are both palindromes.
In fact, these are the only palindromes!
Problem 9.48.
Let \(w\in \Sigma^*\text{.}\)

{(i)}.
If \(w\) is even, show that \(w\) is a palindrome if and only if there is a \(u\in \Sigma^*\) such that \(w = uu^R\text{.}\)

{(ii)}.
If \(w\) is odd, show that \(w\) is a palindrome if and only if there are a \(b\in \Sigma\) and a \(u\in \Sigma^*\) such that \(w = ubu^R\text{.}\)
Problem 9.49.
Below is a list of palindromes. Referring to Problem 9.48 tell, for each one, what \(u\) is if the palindrome has even length and what \(u\) and \(b\) are if it has odd length.
I PREFER PI
A TOYOTAS A TOYOTA
DO GEESE SEE GOD
WAS IT A CAR OR A CAT I SAW
AL LETS DELLA CALL ED STELLA
RATS LIVE ON NO EVIL STAR
DID HANNAH SEE BEES HANNAH DID
IN WORD SALAD ALAS DROWN I