I am trying to figure out a formal grammar for the above language. This language describes palindromes, so it is context-free, if I am not wrong. I came up with a context-sensitive grammar, but I can not find a context-free one. Any ideas?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ This language is not context free, so a context free grammar for it is impossible. It is a context sensitive language, however. $\endgroup$– vonbrandJan 31, 2020 at 18:09
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
The languages of all palindromes is context-free.
That does not implies that any language that contains only palindromes is context-free. For example, many language over the unary alphabet $\{a\}$ are not context-free. In fact, they can even be non-context-sensitive or undecidable. Note that any word over a unary alphabet is a palindrome.
In particular, the language of all words like $a^nb^na^n$ is not context-free. The rough intuition to understand why it is not context-free is that a PDA cannot remember two unbounded independent relations. You can either use the pumping lemma to prove that fact.
Exercise. Give an example of a unary language that is not context-free.
-
$\begingroup$ How about $\{a^{\Sigma(n)} \colon n \ge 1\}$, where $\Sigma$ is Radó's noncomputablr busy-beaver function? $\endgroup$– vonbrandFeb 16, 2020 at 4:01
$\begingroup$
$\endgroup$
How about $\{a^{\Sigma(n)} \colon n \ge 1\}$, where $\Sigma$ is Radó's noncomputablr busy-beaver function?
