Palindrome - Computation Theory

Computation Theory

In the automata theory, a set of all palindromes in a given alphabet is a typical example of a language that is context-free, but not regular. This means that it is, in theory, impossible for a computer with a finite amount of memory to reliably test for palindromes. (For practical purposes with modern computers, this limitation would apply only to incredibly long letter-sequences.)

In addition, the set of palindromes may not be reliably tested by a deterministic pushdown automaton which also means that they are not LR(k)-parsable or LL(k)-parsable. When reading a palindrome from left-to-right, it is, in essence, impossible to locate the "middle" until the entire word has been read completely.

It is possible to find the longest palindromic substring of a given input string in linear time.

Read more about this topic:  Palindrome

Famous quotes containing the words computation and/or theory:

    I suppose that Paderewski can play superbly, if not quite at his best, while his thoughts wander to the other end of the world, or possibly busy themselves with a computation of the receipts as he gazes out across the auditorium. I know a great actor, a master technician, can let his thoughts play truant from the scene ...
    Minnie Maddern Fiske (1865–1932)

    There never comes a point where a theory can be said to be true. The most that one can claim for any theory is that it has shared the successes of all its rivals and that it has passed at least one test which they have failed.
    —A.J. (Alfred Jules)