# reversal

Let $\Sigma$ be an alphabet and $w$ a word over $\Sigma$. The reversal of $w$ is the word obtained from $w$ by “spelling” it backwards. Formally, the reversal is defined as a function $\operatorname{rev}:\Sigma^{*}\to\Sigma^{*}$ such that, for any word $w=a_{1}\cdots a_{n}$, where $a_{i}\in\Sigma$, $\operatorname{rev}(w):=a_{n}\cdots a_{1}$. Furthermore, $\operatorname{rev}(\lambda):=\lambda$. Oftentimes $w^{R}$ or $\operatorname{mi}(w)$ is used to denote the reversal of $w$.

For example, if $\Sigma=\{a,b\}$, and $w=aababb$, then $\operatorname{rev}(w)=bbabaa$.

Two properties of the reversal are:

• it fixes all $a\in\Sigma$: $\operatorname{rev}(a)=a$.

• it is idempotent: $\operatorname{rev}\circ\operatorname{rev}=1$, and

• it reverses concatenation: $\operatorname{rev}(ab)=\operatorname{rev}(b)\operatorname{rev}(a)$.

In other words, the reversal is an antihomomorphism. In fact, it is the antihomomorphism that fixes every element of $\Sigma$. Furthermore, $g$ is an antihomomorphism iff $g\circ\operatorname{rev}$ is a homomorphism. By the second property above, $h$ is a homomorphism iff $h\circ\operatorname{rev}$ is an antihomomorphism.

A word that is fixed by the reversal is called a palindrome. The empty word $\lambda$ as well as any symbol in the alphabet $\Sigma$ are trivially palindromes. Also, for any word $w$, the words $wx\operatorname{rev}(w)$ and $\operatorname{rev}(w)xw$ are both palindromes, where $x$ is either a symbol in $\Sigma$ or the empty word. In fact, every palindrome can be written this way.

The language consisting of all palindromes over an alphabet is context-free, and not regular if $\Sigma$ has more than one symbol. It is not hard to see that the productions are $\sigma\to\lambda$, $\sigma\to a$ and $\sigma\to a\sigma a$, where $a$ ranges over $\Sigma$.

Reversal of words can be extended to languages: let $L$ be a language over $\Sigma$, then

 $\operatorname{rev}(L):=\{\operatorname{rev}(w)\mid w\in L\}.$

A family $\mathscr{F}$ of languages is said to be closed under reversal if for any $L\in\mathscr{F}$, $\operatorname{rev}(L)\in\mathscr{F}$. It can be shown that regular languages, context-free languages, context-sensitive languages, and type-0 languages are all closed under reversal.

Title reversal Reversal 2013-03-22 18:55:20 2013-03-22 18:55:20 CWoo (3771) CWoo (3771) 12 CWoo (3771) Definition msc 68Q70 msc 68Q45 mirror image Palindrome