1
$\begingroup$

This question already has an answer here:

Is $L = \{A^n B^n C^n \mid n \in \mathbb{N}\}$ a context-free language, e.g. $AAAABBBBCCCC \in L$

If so, what's that context-free grammar that produces it?

|cite|improve this question
$\endgroup$

marked as duplicate by Luke Mathieson, Yuval Filmus, Wandering Logic, sdcvvc, Raphael♦ Jul 22 '13 at 13:58

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from cstheory.stackexchange.com Jul 22 '13 at 8:03

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ No, it is not... $\endgroup$ – MCH Jul 22 '13 at 0:01
  • $\begingroup$ @MCH Where can I find a proof that it's not? $\endgroup$ – Nick Mpora Jul 22 '13 at 0:01
  • 2
    $\begingroup$ As MCH notes, this language is not context-free, so there's no point looking for a CFG for it. This language is a standard example of a non-context-free language. To show that it isn't context-free, have a look at our reference question, which has all the basic tools, and some examples which are very similar to $L$. Conversely, to determine which class it is in fact in, you need to demonstrate an appropriate grammar or machine that generates it. (cont.) $\endgroup$ – Luke Mathieson Jul 22 '13 at 8:58
  • 2
    $\begingroup$ Voting to close. Please check lecture notes on context-free languages, where you will find this example worked out using the pumping lemma. $\endgroup$ – Yuval Filmus Jul 22 '13 at 12:36
  • 1
    $\begingroup$ possible duplicate of How can I prove this language is not context-free? and How to prove that a language is not context-free? $\endgroup$ – Wandering Logic Jul 22 '13 at 13:30