What is the difference between a context-sensitive grammar and a context-free grammar?

A context-sensitive grammar and a context-free grammar are both types of formal grammars used in the field of formal languages. However, they differ in terms of the rules and restrictions they impose on the structure of a language.

A context-free grammar (CFG) is a formal grammar where each production rule has a single non-terminal symbol on the left-hand side and a string of terminals and non-terminals on the right-hand side. The key characteristic of a CFG is that the left-hand side non-terminal can be replaced by the right-hand side string in any context, without considering the surrounding symbols. In other words, the production rules of a CFG are not influenced by the context in which they are applied. Examples of context-free languages include regular languages and many programming languages.

On the other hand, a context-sensitive grammar (CSG) is a formal grammar where the production rules are more flexible and can be influenced by the context in which they are applied. In a CSG, the left-hand side non-terminal can be replaced by the right-hand side string, but this replacement is subject to certain conditions based on the surrounding symbols. These conditions can be in the form of restrictions on the length of the context or specific patterns that need to be satisfied. CSGs are more expressive than CFGs and can describe a wider range of languages, including natural languages and some programming languages.

In summary, the main difference between a context-sensitive grammar and a context-free grammar lies in the restrictions imposed on the production rules. While a context-free grammar allows for arbitrary replacements of non-terminals, a context-sensitive grammar considers the context in which these replacements occur, leading to more powerful language description capabilities.