Let be an alphabet and a word over . The reversal of is the word obtained from by “spelling” it backwards. Formally, the reversal is defined as a function such that, for any word , where , . Furthermore, . Oftentimes or is used to denote the reversal of .
For example, if , and , then .
Two properties of the reversal are:
In other words, the reversal is an antihomomorphism. In fact, it is the antihomomorphism that fixes every element of . Furthermore, is an antihomomorphism iff is a homomorphism. By the second property above, is a homomorphism iff is an antihomomorphism.
A word that is fixed by the reversal is called a palindrome. The empty word as well as any symbol in the alphabet are trivially palindromes. Also, for any word , the words and are both palindromes, where is either a symbol in or the empty word. In fact, every palindrome can be written this way.
Reversal of words can be extended to languages: let be a language over , then
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.
|Date of creation||2013-03-22 18:55:20|
|Last modified on||2013-03-22 18:55:20|
|Last modified by||CWoo (3771)|