Context-sensitive grammar
Encyclopedia : C : CO : CON : Context-sensitive grammar
A context-sensitive grammar is a formal grammar G = (N, Σ, P, S) such that all rules in P are of the form
- αAβ → αγβ
- S → ε
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. This is different from a context-free grammar where the context of a nonterminal is not taken into consideration. A formal language that can be described by a context-sensitive grammar is called a context-sensitive language.
The concept of context-sensitive grammar was introduced by Noam Chomsky in the 1950s as a way to describe the syntax of natural language where it is indeed often the case that a word may or may not be appropriate in a certain place depending upon the context.
Alternative definition
Another definition of context-sensitive grammars defines them as formal grammars with the restriction that for all rules α -> β in P it holds that |α| ≤ |β| where |α| is the length of α. Such a grammar is also called a monotonic or noncontracting grammar because none of the rules decreases the size of the string that is being rewritten.While the noncontracting grammars are different from the context-sensitive ones, the two are almost equivalent in the sense that they define the same class of languages (except that noncontracting grammars cannot generate any language that contains the empty string ε). But if a formal language L can be described by a grammar of the first definition then there is a noncontracting grammar that describes L - , and vice versa.
Example
A simple monotonic grammar is- S → abc | aSBc
- cB → Bc
- bB → bb
Normal forms
Computational properties and Uses
The decision problem that asks whether a certain string s belongs to the language of a certain context-sensitive grammar G, is PSPACE-complete. Indeed, there are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete.It has been shown that nearly all natural languages may in general be characterized by context-sensitive grammars, however the whole class of CSG's seems to be much bigger than natural languages. Worse yet, since the aforementioned decision problem for CSG's is PSPACE-complete, that makes them totally unworkable for practical use, as the general algorithm would take exponential time. Ongoing research on computational linguistics has focused on formulating other classes of languages that are "mildly context-sensitive" whose decision problems are feasible, such as tree-adjoining grammars, coupled context-free languages, and linear context-free rewriting systems. The languages generated by these formalisms properly lie between the context-free and context-sensitive languages.
See also: Chomsky hierarchy
| Automata theory: formal languages and formal grammars | |||
|---|---|---|---|
| Chomsky hierarchy | Grammars | Languages | Minimal automaton |
| Type-0 | Unrestricted | Recursively enumerable | Turing machine |
| n/a | (no common name) | Recursive | Decider |
| Type-1 | Context-sensitive | Context-sensitive | Linear-bounded |
| Type-2 | Context-free | Context-free | Pushdown |
| Type-3 | Regular | Regular | Finite |
| Each category of languages or grammars is a proper subset of the category directly above it. | |||
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.