2
$\begingroup$

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?

$\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$
    – vonbrand
    Jan 31 '20 at 18:09
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ How about $\{a^{\Sigma(n)} \colon n \ge 1\}$, where $\Sigma$ is Radó's noncomputablr busy-beaver function? $\endgroup$
    – vonbrand
    Feb 16 '20 at 4:01
0
$\begingroup$

How about $\{a^{\Sigma(n)} \colon n \ge 1\}$, where $\Sigma$ is Radó's noncomputablr busy-beaver function?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.