We have to sort of reign it in just a little and make the problem more generic, too. So, let's say that we have one language P, a subset of a more generally-defined language comprised of only those recognizable phrases which are palindromes. It's fairly easy to arbitrarily generate phrases from a given grammar and lexicon but doing so in such a way that it remains a palindrome is somewhat challenging, but doing so in such a way that it remains syntactically correct is what we're interested in here.

Consider the following simple grammar:

S -> AThis grammar only generates strings of x's, so of course it only generates palindromes, and it can also generate arbitrarily-long strings. This is a patently ridiculous grammar but it does demonstrate one issue: how do you prove that your grammar even has a maximum-length palindrome? Consider the following grammar:

A -> x A

| x

S -> AThat grammar produces an infinite number of phrases, none of them palindromes. How complicated is it to prove the existence or nonexistence of palindromes in a well-defined language?

A -> x y A

| x y

Because it reminds me of some aspects of the Busy Beaver Problem, perhaps a version of the Busy Beaver Problem for push-down automata. If anyone's heard of it or better yet a proof of its complexity, let me know.

Thinking too much as always. Sleep tight, space cadets.

## No comments:

Post a Comment