reversal


Let Σ be an alphabet and w a word over Σ. The reversal of w is the word obtained from w by “spelling” it backwards. Formally, the reversal is defined as a function rev:Σ*Σ* such that, for any word w=a1an, where aiΣ, rev(w):=ana1. Furthermore, rev(λ):=λ. Oftentimes wR or mi(w) is used to denote the reversal of w.

For example, if Σ={a,b}, and w=aababb, then rev(w)=bbabaa.

Two properties of the reversal are:

  • it fixes all aΣ: rev(a)=a.

  • it is idempotentMathworldPlanetmathPlanetmath: revrev=1, and

  • it reverses concatenationMathworldPlanetmath: rev(ab)=rev(b)rev(a).

In other words, the reversal is an antihomomorphismMathworldPlanetmath. In fact, it is the antihomomorphism that fixes every element of Σ. Furthermore, g is an antihomomorphism iff grev is a homomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath. By the second property above, h is a homomorphism iff hrev is an antihomomorphism.

A word that is fixed by the reversal is called a palindrome. The empty wordPlanetmathPlanetmathPlanetmath λ as well as any symbol in the alphabet Σ are trivially palindromes. Also, for any word w, the words wxrev(w) and rev(w)xw are both palindromes, where x is either a symbol in Σ or the empty word. In fact, every palindrome can be written this way.

The languagePlanetmathPlanetmath consisting of all palindromes over an alphabet is context-free, and not regularPlanetmathPlanetmathPlanetmath if Σ has more than one symbol. It is not hard to see that the productions are σλ, σa and σaσa, where a ranges over Σ.

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

rev(L):={rev(w)wL}.

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

Title reversal
Canonical name Reversal
Date of creation 2013-03-22 18:55:20
Last modified on 2013-03-22 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