# Palindromes and linear grammars

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

• 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. – D.W. Feb 21 '14 at 0:02

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.