Project: Reversed Strings and Palindromes

David M. Clark and W. Ted Mahavier

( Chapter 3: W. Ted Mahavier < E.L. May < K.M. Shannon ¹ )

If each of \(X\) and \(Y\) is a person, then the relation \(X < Y\) indicates that the notes originated with \(Y\) and were subsequently modified by \(X\text{,}\) who takes full responsibility for the current version. While \(Y\) is credited with the genesis of the notes, s/he makes no claim to the accuracy of the current version which may or may not reflect her/his original version.

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