Is it possible to make an algebraic grammar LL($1$) which recognizes palindroms for an alphabet $\{a,b\}$?
Add a comment
|
$\begingroup$
$\endgroup$
3
No. The language of palindromes over any alphabet with at least two elements is not deterministic, and thus has no LR or LL grammar.
The language of even-length palindromes $L_{epal}=\{ww^R \mid w\in\Sigmạ^*\}$ is a classic example of a non-deterministic context-free language, and you can find the outline of a proof in Hopcroft & Ullman (and other standard texts). The restriction to even-length palindromes simplifies the proof, but it can be extended to the language of all palindromes $L_{pal}=\{w \mid w=w^R, w\in\Sigmạ^* \}$. Without doing more work, though, it's evident that $L_{epal}=L_{pal}\cap (\Sigma\Sigma)^*$, and deterministic CFLs are closed against intersection with regular languages.
-
$\begingroup$ Thanks for your answer. Could you give me a source or an argument please? $\endgroup$ – Ievgeni Feb 17 at 15:08
-
-
