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

Formal Languages Questions



80 Short 63 Medium 57 Long Answer Questions Question Index

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

The main difference between a context-free grammar and a context-sensitive grammar lies in the restrictions imposed on the production rules.

In a context-free grammar, the left-hand side of each production rule consists of a single non-terminal symbol, while the right-hand side can be any combination of terminal and non-terminal symbols. The production rules are not influenced by the context or surrounding symbols, hence the name "context-free". Context-free grammars are less expressive than context-sensitive grammars.

On the other hand, in a context-sensitive grammar, the left-hand side of each production rule can be a combination of terminal and non-terminal symbols, and the right-hand side can be any combination of symbols. The production rules are influenced by the context or surrounding symbols, hence the name "context-sensitive". Context-sensitive grammars are more expressive than context-free grammars and can describe a wider range of languages.