1
$\begingroup$

Given a context-free grammar G. Is it decidable, if the language $L(G)$, which is generated by G, contains a palindrome?

My suggestion is, that it is undecidable, but I do not have an idea for a formal prove. Any hints?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ It can be proved undecidable using the fact that we cannot decide whether two CF languages have a nonempty intersection. Or, whether the Post Correspondence Problem has a solution; the latter will lead to undecidability even for the subfamily of linear languages: Palindromes and linear grammars $\endgroup$
    – Hendrik Jan
    Commented Dec 2, 2017 at 20:11

0

Reset to default