The goal of this homework is to refresh your discrete math skills, and to accustomize you to seeing strings as

mathematical objects. We are going to use these skills later on when analyzing languages and automata.

$(4$ points$)$ Prove that string reversal ${(}^R)$ is an involution. That is$,(w^R{)}^R=w$ for any given string.

$(4$ points$)$ Prove that, for any given string $w$ if

$w$ is a palindrome $($that is $w=w^R),$ and

$|w|$ is even

then there is a string $v$ such that $v{v}^R=w.$

$(4$ points$)$ Bonus question

A string is repeat$-$free if non$-$empty prefixes of the string does not occur in the rest of the string. That is$,w$ is

repeat$-$free if for all $x,y,$ if $xy=w$ then $x$ does not occur in $y.$

How many repeat$-$free strings of length $n$ are there for each of the following alphabets? Show your work.

The binary alphabet $\{0,1\}$

The ternary alphabet $\{0,1,2\}$