A context-sensitive grammar is a formal grammar such that all its rules are of the form αAβ → αγβ with nonterminal A and α and β strings of nonterminals and terminals. The name context-sensitive is explained by the α and β that form the context of A and determine whether A can be replaced with γ or not. Context sensitive languages can be accepted by linear bounded automata.
Related categories 1
Context Sensitive Languages and Linear Bounded Automata
A set of slides defining these terms and showing that context sensitive languages are accepted by linear bounded automata.
Grammars for three context sensitive languages that are not context free. [PDF]
A Wikipedia article which defines context sensitive languages in terms of context sensitive grammars which are defined in a linked article.
Processing Natural and Formal Languages
Lecture notes from a course at the University of Edinburgh, covering processing natural and artificial languages.
Last update:January 2, 2007 at 19:58:46 UTC