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 = \lbrace a, b\rbrace$ , 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)$ .

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):= \lbrace \operatorname{rev}(w) \mid w\in L\rbrace.$$

A family of languages is said to be closed under reversal if for any , . It can be shown that regular languages, context-free languages, context-sensitive languages, and type-0 languages are all closed under reversal.