You are here
Homereversal
Primary tabs
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 contextfree, 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, contextfree languages, contextsensitive languages, and type0 languages are all closed under reversal.
Mathematics Subject Classification
68Q70 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections