Context-sensitive grammar

A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols.

Uses your system voice; voice and rate in settings.

≈ 6 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context-sensitive grammars are more general than context-free grammars, in the sense that there are languages that can be described by a CSG but not by a context-free grammar.

Context-sensitive grammars are less general (in the same sense) than unrestricted grammars. Thus, CSGs are positioned between context-free and unrestricted grammars in the Chomsky hierarchy. A formal language that can be described by a context-sensitive grammar, or, equivalently, by a noncontracting grammar or a linear bounded automaton, is called a context-sensitive language.

Some textbooks actually define CSGs as non-contracting, although this is not how Noam Chomsky defined them in 1959. This choice of definition makes no difference in terms of the languages generated (i.e. the two definitions are weakly equivalent), but it does make a difference in terms of what grammars are structurally considered context-sensitive; the latter issue was analyzed by Chomsky in 1963.

Chomsky introduced context-sensitive grammars as a way to describe the syntax of natural language where it is often the case that a word may or may not be appropriate in a certain place depending on the context. Walter Savitch has criticized the terminology "context-sensitive" as misleading and proposed "non-erasing" as better explaining the distinction between a CSG and an unrestricted grammar.

Although it is well known that certain features of languages (e.g. cross-serial dependency) are not context-free, it is an open question how much of CSGs' expressive power is needed to capture the context sensitivity found in natural languages. Subsequent research in this area has focused on the more computationally tractable mildly context-sensitive languages.

The syntaxes of some visual programming languages can be described by context-sensitive graph grammars.

Formal definition

Let us notate a formal grammar as G = (N, \Sigma, P, S) , with N a set of nonterminal symbols, \Sigma a set of terminal symbols, P a set of production rules, and S \in N the start symbol. A string u \in (N \cup \Sigma)^* directly yields, or directly derives to, a string v \in (N \cup \Sigma)^* , denoted as u \Rightarrow v , if v can be obtained from u by an application of some production rule in P, that is, if u = \gamma L \delta and v = \gamma R \delta , where (L \to R) \in P is a production rule, and \gamma, \delta \in (N \cup \Sigma)^* is the unaffected left and right part of the string, respectively.

More generally, u is said to yield, or derive to, v, denoted as u \Rightarrow^* v , if v can be obtained from u by repeated application of production rules, that is, if u = u_0 \Rightarrow ... \Rightarrow u_n = v for some n ≥ 0 and some strings u_1, ..., u_{n-1} \in (N \cup \Sigma)^* . In other words, the relation \Rightarrow^* is the reflexive transitive closure of the relation \Rightarrow .

The language of the grammar G is the set of all terminal-symbol strings derivable from its start symbol, formally: L(G) = \{ w \in \Sigma^* \mid S \Rightarrow^* w \} . Derivations that do not end in a string composed of terminal symbols only are possible, but do not contribute to L(G). A non contracting grammar (for which there is an equivalent CSG) for the language L_{Cross} = \{ a^mb^nc^{m}d^{n} \mid m \ge 1, n \ge 1 \} is defined by p_0 : S \rightarrow RT , p_1 : R\rightarrow aRC | aC , p_3 : T\rightarrow BTd | Bd , p_5 : CB\rightarrow BC , p_6 : aB\rightarrow ab , p_7 : bB\rightarrow bb , p_8 : Cd\rightarrow cd , and p_9 : Cc\rightarrow cc .

With these definitions, a derivation for a^3b^2c^3d^2 is: S \Rightarrow_{p_0} RT \Rightarrow_{p^{2}_{1}p_{2}} a^3C^3T \Rightarrow_{p_{3}p_{4} } a^3C^3B^2d^2 \Rightarrow_{p^{6}_{5} } a^3B^2C^3d^2 \Rightarrow_{p_{6}p_{7} } a^3b^2C^3d^2 \Rightarrow_{p_{8}p^{2}_{9}} a^3b^2c^3d^2 . The emptiness problem for context-sensitive grammars (given a context-sensitive grammar G, is L(G)=∅ ?) is undecidable.

It has been shown that nearly all natural languages may in general be characterized by context-sensitive grammars, but the whole class of CSGs seems to be much bigger than natural languages. Worse yet, since the aforementioned decision problem for CSGs is PSPACE-complete, that makes them totally unworkable for practical use, as a polynomial-time algorithm for a PSPACE-complete problem would imply P=NP.

It was proven that some natural languages are not context-free, based on identifying so-called cross-serial dependencies and unbounded scrambling phenomena. However this does not necessarily imply that the class of CSGs is necessary to capture "context sensitivity" in the colloquial sense of these terms in natural languages.

For example, linear context-free rewriting systems (LCFRSs) are strictly weaker than CSGs but can account for the phenomenon of cross-serial dependencies; one can write a LCFRS grammar for {a n b n c n d n | n ≥ 1} for example. 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, combinatory categorial 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. More recently, the class PTIME has been identified with range concatenation grammars, which are now considered to be the most expressive of the mild-context sensitive language classes.

See also

Chomsky hierarchy Growing context-sensitive grammar Definite clause grammar#Non-context-free grammars List of parser generators for context-sensitive grammars

Earley Parsing for Context-Sensitive Grammars

Text derived from https://en.wikipedia.org/w/index.php?oldid=1368790723 under CC BY-SA 4.0; modifications have been made.

Words in each sectionFormal definitionFormal definitionFormal definition: 627 words627See alsoSee alsoSee also: 17 words17
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001368790723 · captured 2026-08-11 · ledger · version history

Cite this page as: encyclopegia.org, “Context-sensitive grammar”, snapshot enwiki-001368790723. https://encyclopegia.org/a/context-sensitive-grammar

Sources cited in this revision

15 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.