Search code examples
context-free-language

Find out if language is context-free or not

If I have {a^n b^n c^n | n > 0} \sum = {a,b,c}, how can I prove if it's a context-free language?

I looked here: Determine if a language is context free, but doesn't make much sense to me.

I believe it is if I do 

<S> ::= <A><B><C>|abc
<A> ::= a<A>
<B> ::= b<B>
<C> ::= c<C>

But I'm not sure. Any help would be appreciated!

Solution

  • There is no algorithm for determining whether a language is context free. Finding a context free grammar is, of course, sufficient but there is no algorithm for doing that, so it is dependent on skill, intuition and luck.

    The language anbncn is well-known to not be context-free; you can prove that with the pumping lemma, and since it is a common example, you can probably find a proof fairly easily with Google.

    You proposed grammar does not guarantee that the number of a's, b's and c's are equal. It matches any string consisting of some a's followed by some b's followed by some c's. (Or better said, it would do that if you made the A, B, and C productions useful by adding non-recursive base cases.) It is the three-way count agreement which makes the language not context-free.