[Solved]: Give a grammar to show whether a language is regular or context-free

Problem Detail: 

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 ?

Asked By : user1934980

Answered By : Karolis Juodelė

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9418