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.
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
Among aperiodic words, the largest possible palindromic density is achieved by the Fibonacci word, which has density 1/φ, where φ is the Golden ratioDOWNLOAD SOLUTION HERE