Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have to generate a grammar for the language $L = \{ w \in \{ a, b\}^* \mid |w| \in 2\mathbb{N}, w \neq w^R\}$ and give the type of the language.

I've generated the grammar

$\qquad \begin{align} S &\to aSa \mid bSb \mid aAb \mid bAa \\ A &\to abA \mid baA \mid aaA \mid bbA \mid \varepsilon \end{align}$

This grammar is a context free grammar. I now can say that $L$ is a context free language. But how can I say for sure that this language isn't regular ?

share|cite|improve this question
First, you need to prove that your grammar really generates $L$, otherwise you know nothing. Second, see here for multiple techniques for showing that some language is not regular. – Raphael Feb 2 '13 at 14:18
up vote 4 down vote accepted

Regular languages are closed under complement and intersection. The complement of $L$, intersected with the regular $\{w : |w| \equiv 0 \pmod{2}\}$ is the language of even palindromes. If you must, you can easily show that it is not regular using pumping lemma.

share|cite|improve this answer
Could you please tell me how could i use the pumping lemma. I know that it's used to show that a language it's not regular.I use the negated form of the pumping lemma.In order to do so i usually have a language that has a form like a^k b^ k(or something close to that).After this I choose an i so such that xy^iz does not belong to the L.I don't know from where to start with the pumping lemma in this example – user1934980 Feb 2 '13 at 12:56
i've managed to demonstrate that palindromes are not regular.Thanks for the tip :) – user1934980 Feb 2 '13 at 13:29
@user1934980, it would be hard to apply pumping lemma to $L$ directly, because so few words (of even length) don't belong to it. That is why I suggested to assume it is regular, transform it and then show a contradiction. – Karolis Juodelė Feb 2 '13 at 13:31

Your grammar is almost correct except for the fact that you cannot derive any word. Thus, it produces the empty language. However, as I said, the idea to produce a "difference" and then switch to another nonterminal is correct.

To prove that a language (no matter which one) is not regular, you can use the pumping lemma or, if you need it a little simpler, a proof by contradiction using a pumping argument.

Note, however, that the pumping lemma cannot be used to prove the converse.

share|cite|improve this answer

Language categories are sets, and the context-free language set contains the regular language set. In other words, every regular language is context-free. It's useful to know that context-free contains LR, which contains LL, which contains regular.

Your language is regular because its definition conforms to the regular definition (strings that can be formed over an alphabet by applying the operations of concatenation, union, and closure).

There's an algorithm for converting a regular definition into a grammar. I believe that the algorithm would produce the following grammar for your language:

S -> aS
S -> bS
S -> ε

I'm not quite sure that the grammar you posted corresponds to the regular language definition. It's better to stick to proven stuff.

share|cite|improve this answer
No, this grammar would produce all words over a,b. – Dan Feb 2 '13 at 14:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.