Context free grammar for palindrome over ALL terminals?

1.1k Views Asked by At

I've found various examples of context-free grammars for palindromes but they all seem to hardcode the rules to be of the form "terminal Statement (same) terminal"

For example, if $T \rightarrow a | b | c$ and we wanted to generate any-length palindromes, the grammar rules would be $S \to aSa \mid bSb \mid cSc \mid T \mid \epsilon$

Is there way to make a generalized rule rather than individually listing $aSa$, $bSb$, ... for every terminal character?

1

There are 1 best solutions below

0
On

As stated by @saulspatz:

"If you say, "One can substitute a for the second X provided one has substituted a for the first X", then the permitted substitutions depend on the context, don't they?"

By nature of being context free, a general rule for such a thing is not possible. It must be explicitly specified by doing something like "aSa"