HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Give a grammar to show whether a language is regular or context-free

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
showfreeregulargivelanguagegrammarcontextwhether

Problem

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 ?

Solution

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.

Context

StackExchange Computer Science Q#9418, answer score: 4

Revisions (0)

No revisions yet.