1
$\begingroup$

Given a linear grammar G, is it possible to determine if L(G) contains a palindrome?

$\endgroup$
1
  • $\begingroup$ What do you think? What have you tried? What research have you done? We normally expect you to do some research on your own before asking and to show what you've tried in the question. $\endgroup$ – D.W. Feb 21 '14 at 0:02
6
$\begingroup$

Consider Post correspondence problem (PCP). If $\alpha_1 \dots \alpha_n$ and $\beta_1 \dots \beta_n$ are the words of PCP, then $S \to \alpha_iS\beta_i^r$ and $S \to \#$ where $\#$ is a symbol not in any of $\alpha_i, \beta_i$ and $s^r$ is the string $s$ reversed, gives a grammar $G$ such that if $G$ generates a palindrome, then the corresponding instance of PCP has a solution. PCP is RE though.

$\endgroup$
1
  • $\begingroup$ You prove it is at best RE. You should add the procedure to actually do it. $\endgroup$ – babou Feb 20 '14 at 16:32

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.