# Why is my regular grammar for palindromes wrong?

I've seen that people prove somehow that set of all palindromes isn't regular language by using a pumping lemma, which I am not familiar with.

I've created grammar which can generate all palindromes and that is why I wonder why it's wrong.

A -> e
A -> a | b | ... | z
A -> aAa | bAb | ... | zAz

• Your grammar is correct, but context free grammars generate context-free languages, which strictly contain the regular languages. Regular languages are exactly those recognized by deterministic finite automata (or some equivalent model, such as NFAs or regular grammars). Jan 28 '16 at 8:44

Your grammar is correct, in the sense that it does generate all palindromes over the alphabet $\{a, \dots, z\}$. But it's a context-free grammar and not a regular grammar. In a regular grammar, you're only allowed rules of the form $A\to\epsilon$, $A\to a$ and $A\to aB$, i.e., there is at most one non-terminal on the right and any terminals must come before it.
• IIRC, mixing $A \to aB$ and $A \to Ba$ rules does not get you above REG. The proof for left-linear being as powerful as right-linear should apply to parts of a grammar.
• Mixing does get you above REG, since any rule $A\to aAa$ can be decomposed into $A\to aX_a$ and $X_a\to Aa$. Jan 28 '16 at 13:24