Problem Detail: I have to generate a grammar for the language $L = { w in { a, b}^* mid |w| in 2mathbb{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
