Why is this not context free grammar?

I vaguely recall { a^n b^n c^n is, n>=0 } not context free.

But isn't the following a valid context free grammar that captures the above

S -> abcS S -> null

Quoting Wikipedia:

"In formal language theory, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and开发者_StackOverflow w is a string of terminals and/or nonterminals (w can be empty)."

S -> abcS produces something like that (abc)^n not a^n b^n c^n

Just in case you are wondering why it's not a context free grammar, here's a quick explanation:

A context free grammar is a grammar that can be recognized by a push-down automaton, which is a finite state automaton with the addition of a stack.

An example of a CFG is a^n b^n. If you think about it, we can push a token on our stack for every 'a' that we see and pop a token off the stack for every 'b' we see. We will fail at any point if we - push a token after popping (a 'b' followed by an 'a') - finish processing the string but we still have tokens on the stack (more 'a's than 'b's) - try to pop an empty stack (more 'b's than 'a's)

If you think about how to recognize a^n b^n c^n with a push-down automaton, you will probably realize that is impossible after some playing around.

Hope that helps.

You've written a production rule that generates abc^n, not a^n b^n c^n.

For n=2 shouldn't the production be: aabbcc? But wouldn't your example grammar produce abcabc?