## SectionProject: Reversed Strings and Palindromes

###### Definition9.40.

If $w\in \Sigma^*\text{,}$ we define $w^R\in \Sigma^*$ recursively as follows.

1. $\lambda^R = \lambda$ and $a^R = a$ for all $a\in \Sigma\text{.}$

2. If $w = av$ where $a\in \Sigma$ and $v\in \Sigma^*\text{,}$ then $w^R = v^Ra\text{.}$

###### Problem9.41.

Use Definition 9.40 to compute $w^R$ if $w=pots\text{.}$ What is $w^R$ if $w = scitamehtametercsid\text{?}$

###### Problem9.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.

###### Problem9.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.

###### Problem9.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.

###### Definition9.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.

###### Problem9.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{.}$

###### Problem9.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!

###### Problem9.48.

Let $w\in \Sigma^*\text{.}$

1. ###### {(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{.}$

2. ###### {(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{.}$

###### Problem9.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