reversal
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:
-
•
it fixes all : .
-
•
it is idempotent: , and
-
•
it reverses concatenation: .
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.
The language consisting of all palindromes over an alphabet is context-free, and not regular if has more than one symbol. It is not hard to see that the productions are , and , where ranges over .
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.
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 |