patternMinor
Give a grammar to show whether a language is regular or context-free
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 ?
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.