Palindrome
A palindrome (from Greek Παλίνδρομος palíndromos, running backwards ') is a string that can be read from the front and rear remains the same.
- 3.1 Definition
- 3.2 Symmetric decomposition
- 3.3 Recognition of palindromes
- 3.4 Recursive Definition
- 3.5 Context-free grammar for palindromes
Importance
Palindromes do not always have a sense result, the string must, however, from front to back and from back to front with respect to the sequence of characters used to match.
In addition, words, strings of words or phrases are called palindromes, which read backwards have meaning (such as the words stock - shelf ). In this broader sense, the palindrome is a special form of the anagram. Related to the palindrome is the ambigram, which is usually after a 180 ° rotation still gives the same word.
According to the Guinness Book of Records 1997, the longest German one-word palindrome relief pillar is ( dt for pilasters ). This Wortpalindrom has no particular significance as art historical term. The compound is viewed as being a remarkable palindrome, because a long one-word palindrome in the German language is rare. The compound is already being mentioned as an example in Meyer's Big Conversation Lexicon of 1905. His "discovery" is often attributed to the philosopher Arthur Schopenhauer - a claim that closer examination, however, does not stand up. Longer than relief pillars, however, the word Retsinakanister. As the longest Wortpalindrom everyday language is Finnish Saippuakivikauppias ( soapstone seller).
Palindromes do not necessarily only consist of letters. Thus, there are Zahlenpalindrome seen from the front or rear give the same value (about 2442 ), music palindromes and pieces of music that is, forward and reverse play, listen (because of fading away of sounds almost) equal. Joseph Haydn's Symphony No. 47 in G major is also called " the palindrome " for example. Primes in turn, result in the read differently than Primzahlpalindrome new prime numbers backwards (so no palindromes after strict definition ), is called Mirpzahlen. Also exist date palindrome, such as the 10, 02, 2001 and Zeitpalindrome, for example 13:31.
In genetics palindromic sequences play a role in the conformation of the DNA.
Examples
Wortpalindrome
- Storage rack
- Neozoa
- Otto
- Mount
- Relief pillar
- Pensioner
- Rotor
Otto, mount and rotor are in addition Morse code palindromes because they consist exclusively of symmetric Morse code. Examples of Morsecodepalindrome who found no more palindromes in Latin letters, are you ( - · · · · - ) or ( · -, - · ).
The German poet and children's book author Josef Guggenmos wrote a nursery rhyme about a giant whose name is also a palindrome: The giant " Mutakirorikatum ".
Satzpalindrome
- Love is the winner; always busy she is with sorrow.
- A güldne, good virtue: never lie!
- Erika fires only unfaithful fakirs.
- A donkey never read.
- A negro with gazelle never hesitates in the rain.
- O genius, the Lord honor your ego!
- Tim wore such a bright pants with belt never?
Backward read meaningful
- Eber - Vine
- Fog - life
- Coffin - Grass
- Storage - Storage
Others
Palindromes in the computer science
In theoretical computer science, more precisely, the theory of formal languages , a mathematical formalism for dealing with strings has been developed, which are called in the theoretical context, words.
The definition that a palindrome is a word that spelled backwards again gives the same word, now writes so formal:
Definition
A palindrome is a word over the alphabet with the property
Which means that the operator of mirroring (or reversing the order of characters) is applied to the word. It should be noted that a palindrome not necessarily make sense here; the corresponding word only has to be symmetrical about its center.
Symmetric decomposition
Where
If (word length) is even, or
If is odd, where ( finite words) and (a sign of the alphabet ) is.
This can be seen in each case by substituting, for example:
For example, you can
Decompose with
So that
Recognition of palindromes
The language
(the amount of the finite word length of the words in straight, which are palindrome ) is not regular, ie you can not specify a regular expression which specifies, or no finite state machine (ie a machine with finite memory ) to see who manages ( ie, to decide whether a word for language belongs or not).
As long as desired, albeit finite, words have to be investigated, much memory is potentially unlimited needed to memorize and then subsequently to compare. It can be shown that a non- deterministic pushdown automaton is sufficient to detect, for example, by specifying a concrete context-free grammar. However, there is no deterministic pushdown automaton that recognizes this language.
Recursive definition
The inductive or recursive definition for Palindrome looks like this:
Context-free grammar for palindromes
The above inductive definition is the starting point for the construction of a context-free grammar for palindromes.
To simplify the alphabet was limited to two symbols, ie a binary alphabet. Then one can derive all binary word palindromes with the following productions:
From the start symbol can immediately generate palindromes ( empty word ), and. The remaining palindromes are obtained by first in both directions generates a symmetric word and then replace the non-terminal symbol in the middle of one of the terminal symbols.
- .
Palindrome in molecular genetics
In molecular genetics short DNA fragments are called palindromes when the two strands have the same sequence in opposite directions. These DNA segments are often referred to as restriction enzymes recognition sequence. The enzymes attach to the appropriate section and cut the DNA duplex in a characteristic way by.
For example, the recognition sequence of the enzyme EcoRI
5'- GAATTC -3 ' 3'- CTTAAG -5 ' 5' -G AATTC -3 ' 3'- CTTAA G -5 ' Restriction enzymes are a very important tool in molecular genetics. Because the recognition sequence is characteristic for each enzyme can thus DNA molecules specifically cut. Since the interface is often a few bases long piece is connected via one of the two strands (see sticky ends ), the DNA fragments can also be joined together again in a controlled manner as well.