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 contextfree, 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 $\mathcal{F}$ of languages is said to be closed under^{} reversal if for any $L\in \mathcal{F}$, $\mathrm{rev}(L)\in \mathcal{F}$. It can be shown that regular languages, contextfree languages, contextsensitive languages, and type0 languages are all closed under reversal.
Title  reversal 

Canonical name  Reversal 
Date of creation  20130322 18:55:20 
Last modified on  20130322 18:55:20 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  12 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q70 
Classification  msc 68Q45 
Synonym  mirror image 
Related topic  Palindrome 