2
$\begingroup$

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
$\endgroup$
1
  • 2
    $\begingroup$ 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). $\endgroup$
    – Shaull
    Jan 28 '16 at 8:44
4
$\begingroup$

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.

(Alternatively, you get the same class of languages by insisting that any terminals on the right must come after the nonterminal but you can't mix the two in a single grammar.)

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Jan 28 '16 at 11:08
  • 3
    $\begingroup$ 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$. $\endgroup$ Jan 28 '16 at 13:24

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.