0
$\begingroup$

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?

$\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$
    – Nathaniel
    Apr 7 at 23:05

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.