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?
Asked
Viewed
5k times
1
$\begingroup$
$\endgroup$
-
$\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
