reversal

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

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

Two properties of the reversal are:

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

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

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

In other words, the reversal is an antihomomorphism. In fact, it is the antihomomorphism that fixes every element of $\mathrm{\Sigma }$. Furthermore, $g$ is an antihomomorphism iff $g\circ \mathrm{rev}$ is a homomorphism. By the second property above, $h$ is a homomorphism iff $h\circ \mathrm{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 $\mathrm{\Sigma }$ are trivially palindromes. Also, for any word $w$, the words $wx\mathrm{rev}(w)$ and $\mathrm{rev}(w)xw$ are both palindromes, where $x$ is either a symbol in $\mathrm{\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 $\mathrm{\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 $\mathrm{\Sigma }$.

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

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

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