It is known that the language $\{a^nb^nc^n|n\geq0\}$ is not context-free (we can prove it using the pumping lemma, as shown here: Is $a^n b^n c^n$ context-free?). Yet, this answer claims it has found a context-free grammar for this language. My question is, is it possible to find a context free grammar for a not context-free language?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ The CFG is not given for $L = \{a^nb^nc^n\mid n\geqslant 0\}$ in the post you quote, but for $a^*b^*c^*\setminus L$ which is context-free. $\endgroup$– NathanielApr 7 at 23:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
No. Every context-free grammar generates a context-free language. If you can find a context-free grammar for a language, then the language is context-free.
That assumes the claimed grammar is correct. People claim all sorts of things on the Internet. I wouldn't believe it until you have verified or proven it correct. In this particular case, the answer was incorrect and the grammar doesn't work. I left a comment explaining, and indeed, another answer already responded to that erroneous claim.
