CS402 Theory of Automata GDB Solution Fall 2013

PDA’s are effective tool to represent palindrome as compared to CFG’s.?  give 4-5 line comments in favor or against this.


In the automata theory, a set of all palindromes in a given alphabet is a typical example of a language that is context-free grammar (CFG), but not regular. This means that it is 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.[27][28]

The palindromic density of an infinite word w over an alphabet A is defined to be zero if only finitely many prefixes are palindromes; otherwise, letting the palindromic prefixes be of lengths nk for k=1,2,… we define the density to be

 d_P(w) = \left( { \limsup_{k \rightarrow \infty} \frac{n_{k+1}}{n_k} } \right)^{-1} \ .

Among aperiodic words, the largest possible palindromic density is achieved by the Fibonacci word, which has density 1/φ, where φ is the Golden ratio