1
$\begingroup$

I am new to grammars and I want to learn context free grammars which are the base of programming languages. After solving some problems, I encountered the language

$$\{a^nb^nc^n\mid n\geq 1\}\,.$$

Can anybody tell me if this is a context free language? I can't make any context free grammar for it and I don't know any other proof.

$\endgroup$

marked as duplicate by David Richerby, Ran G., FrankW, Yuval Filmus, Rick Decker Nov 16 '14 at 17:20

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.

  • 3
    $\begingroup$ Welcome to Computer Science Stack Exchange! Your language is a standard example of one that is not context-free. We have a reference question on How to show that a language is not context-free. $\endgroup$ – David Richerby Nov 15 '14 at 23:13
  • 1
    $\begingroup$ perform a search on the tag [context-free]. I found at least 5 question that answer your question. (I recommend to close this question) $\endgroup$ – Ran G. Nov 16 '14 at 4:02
2
$\begingroup$

This is my approach to prove that a given language is not a CFL.

Try hard to come up with a Context free grammar for the given language. If you can come up with such a grammar, then the language is indeed a CFL.

If you can't, then you can use the pumping lemma to show that a given language is not a CFL.

Assume L is context free. Then L satisfies P.L. Then there exists n by the P.L. Let z = a^n b^n c^n Because |z|>=n and z in L, by PL there exist uvwxy s.t.

   z = uvwxy
   |vwx| <= n
   |vx| >= 1
   forall i>=0, u v^i w x^i y in L

But if there exist u,v,w,x,y satisfying the first three constraints, we can show that there exists an i s.t. the fourth constraint fails.

Case uvw consists only of "a". Then when i=0, the string is not in L (fewer "a"s than "b"s or "c"s).

Case vwx contains only "b"s - similar.

Case vwx contains only "c"s - similar.

Case vwx contains only two types of characters from {a,b,c}. Then uwy has more of the remaining type of characters.

The string vw cannot contain "a"s, "b"s, and "c"s, since vwx is a substring of z and has length <=n (cannot contain the last "a" and the first "c" both).i.e this is a contradiction and our assumption is wrong that L is CFL.

$\endgroup$
  • $\begingroup$ Yes, this is the pumping lemma solution for CFL. $\endgroup$ – muradin Nov 16 '14 at 15:30
1
$\begingroup$

You are asking two different questions. First, is $\{a^nb^nc^n : n \geq 1 \}$ a context-free grammar? Second, is $\{a^nb^nc^n : n \geq 1 \}$ a context-free language?

The answer to the first question is No, since $\{a^nb^nc^n : n \geq 1 \}$ is not a grammar, let alone a context-free grammar; it is a language. What you probably meant to ask was: "Does $\{a^nb^nc^n : n \geq 1 \}$ have a context-free grammar?", which is the same as the second question.

The answer to the second question is also No. In fact, it is one of the standard examples of non-context-free languages, and as such most textbooks will have proofs to that effect.

$\endgroup$

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