What does "context" in "context-free grammar" refer to?

Problem Detail: 

There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble:

What context is it free of?

To investigate, I Googled "context sensitive grammar" but I still failed to find what the "context" was all about.

Can someone please explain what the context term refers to in these names?

Asked By : CodyBugstein

Answered By : Vaughn Cato

You are right, there always is a context in some sense. I don't think you can understand what "context" means in "context-free" without understanding a production.

A production is a substitution rule. It says that, to generate strings within the language, you can substitute what is on the left for what is on the right:

A -> xy 

This means that the abstract sequence A can be replaced by the character "x" followed by the character "y". You can also have more complex productions:

zA -> xy 

This means that the character "z" followed by the abstract sequence A can be replaced by the characters "x" and "y".

A context-free production simply means that there is only one thing on the left hand side. The first example is context-free, because A can be replaced by "x" and "y" no matter what comes before or after it. However, in the second example, the character "z" has to appear before the A, and then the combination can be replaced by "x" and "y", so there is some context involved.

A context-free grammar is then just a grammar with only context-free productions.

The second example is actually an example of an unrestricted production. There is another category that is between context-free and unrestricted called "context-sensitive". An example of a context-sensitive production is:

zA -> zxy 

The difference being that what comes before A (and after) on the left hand side has to be preserved on the right. This effectively means that only A is substituted, but can only be substituted in the proper context.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42988