Context-sensitive grammar

A context-sensitive grammar (CSG) is a

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.^[10]

Although it is well known that certain features of languages (e.g.

Let us notate a formal grammar as ${\displaystyle G=(N,\Sigma ,P,S)}$, with ${\displaystyle N}$ a set of nonterminal symbols, ${\displaystyle \Sigma }$ a set of terminal symbols, ${\displaystyle P}$ a set of production rules, and ${\displaystyle S\in N}$ the start symbol.

A string ${\displaystyle u\in (N\cup \Sigma )^{*}}$ directly yields, or directly derives to, a string ${\displaystyle v\in (N\cup \Sigma )^{*}}$, denoted as ${\displaystyle u\Rightarrow v}$, if v can be obtained from u by an application of some production rule in P, that is, if ${\displaystyle u=\gamma L\delta }$ and ${\displaystyle v=\gamma R\delta }$, where ${\displaystyle (L\to R)\in P}$ is a production rule, and ${\displaystyle \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 ${\displaystyle u\Rightarrow ^{*}v}$, if v can be obtained from u by repeated application of production rules, that is, if ${\displaystyle u=u_{0}\Rightarrow ...\Rightarrow u_{n}=v}$ for some n ≥ 0 and some strings ${\displaystyle u_{1},...,u_{n-1}\in (N\cup \Sigma )^{*}}$. In other words, the relation ${\displaystyle \Rightarrow ^{*}}$ is the

${\displaystyle \Rightarrow }$

The language of the grammar G is the set of all terminal-symbol strings derivable from its start symbol, formally: ${\displaystyle 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).

Context-sensitive grammar

A formal grammar is context-sensitive if each rule in P is either of the form ${\displaystyle S\to \varepsilon }$ where ${\displaystyle \varepsilon }$ is the empty string, or of the form

αAβ → αγβ

with A ∈ N,^{[note 1]} ${\displaystyle \alpha ,\beta \in (N\cup \Sigma \setminus \{S\})^{*}}$,^{[note 2]} and ${\displaystyle \gamma \in (N\cup \Sigma \setminus \{S\})^{+}}$.^{[note 3]}

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. By contrast, in a context-free grammar, no context is present: the left hand side of every production rule is just a nonterminal.

The string γ is not allowed to be empty. Without this restriction, the resulting grammars become equal in power to unrestricted grammars.^[10]

(Weakly) equivalent definitions

A noncontracting grammar is a grammar in which for any production rule, of the form u → v, the length of u is less than or equal to the length of v.

Every context-sensitive grammar is noncontracting, while every noncontracting grammar can be converted into an equivalent context-sensitive grammar; the two classes are

The following context-sensitive grammar, with start symbol S, generates the canonical non-context-free language { aⁿbⁿcⁿ | n ≥ 1 } :^{[citation needed]}

Rules 1 and 2 allow for blowing-up S to aⁿBC(BC)ⁿ⁻¹; rules 3 to 6 allow for successively exchanging each CB to BC (

S

→₂ aSBC

→₂ aaSBCBC

→₁ aaaBCBCBC

→₃ aaaBCZCBC

→₄ aaaBWZCBC

→₅ aaaBWCCBC

→₆ aaaBBCCBC

→₃ aaaBBCCZC

→₄ aaaBBCWZC

→₅ aaaBBCWCC

→₆ aaaBBCBCC

→₃ aaaBBCZCC

→₄ aaaBBWZCC

→₅ aaaBBWCCC

→₆ aaaBBBCCC

→₇ aaabBBCCC

→₈ aaabbBCCC

→₈ aaabbbCCC

→₉ aaabbbcCC

→₁₀ aaabbbccC

→₁₀ aaabbbccc

aⁿbⁿcⁿdⁿ, etc.

More complicated grammars can be used to parse { aⁿbⁿcⁿdⁿ | n ≥ 1 }, and other languages with even more letters. Here we show a simpler approach using non-contracting grammars:^{[citation needed]} Start with a kernel of regular productions generating the sentential forms ${\displaystyle (ABCD)^{n}abcd}$ and then include the non contracting productions ${\displaystyle p_{Da}:Da\rightarrow aD}$, ${\displaystyle p_{Db}:Db\rightarrow bD}$, ${\displaystyle p_{Dc}:Dc\rightarrow cD}$, ${\displaystyle p_{Dd}:Dd\rightarrow dd}$, ${\displaystyle p_{Ca}:Ca\rightarrow aC}$, ${\displaystyle p_{Cb}:Cb\rightarrow bC}$, ${\displaystyle p_{Cc}:Cc\rightarrow cc}$, ${\displaystyle p_{Ba}:Ba\rightarrow aB}$, ${\displaystyle p_{Bb}:Bb\rightarrow bb}$, ${\displaystyle p_{Aa}:Aa\rightarrow aa}$.

a^mbⁿc^mdⁿ

A non contracting grammar (for which there is an equivalent CSG) for the language ${\displaystyle L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}\mid m\geq 1,n\geq 1\}}$ is defined by

${\displaystyle p_{1}:R\rightarrow aRC|aC}$,

${\displaystyle p_{3}:T\rightarrow BTd|Bd}$,

${\displaystyle p_{5}:CB\rightarrow BC}$,

${\displaystyle p_{0}:S\rightarrow RT}$,

${\displaystyle p_{6}:aB\rightarrow ab}$,

${\displaystyle p_{7}:bB\rightarrow bb}$,

${\displaystyle p_{8}:Cd\rightarrow cd}$, and

${\displaystyle p_{9}:Cc\rightarrow cc}$.

With these definitions, a derivation for ${\displaystyle a^{3}b^{2}c^{3}d^{2}}$ is: ${\displaystyle S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}}$.^{[citation needed]}

a²ⁱ

A noncontracting grammar for the language { a²ⁱ | i ≥ 1 } is constructed in Example 9.5 (p. 224) of (Hopcroft, Ullman, 1979):^[15]

1. ${\displaystyle S\rightarrow [ACaB]}$
2. ${\displaystyle {\begin{cases}\ [Ca]a\rightarrow aa[Ca]\\\ [Ca][aB]\rightarrow aa[CaB]\\\ [ACa]a\rightarrow [Aa]a[Ca]\\\ [ACa][aB]\rightarrow [Aa]a[CaB]\\\ [ACaB]\rightarrow [Aa][aCB]\\\ [CaB]\rightarrow a[aCB]\end{cases}}}$
3. ${\displaystyle [aCB]\rightarrow [aDB]}$
4. ${\displaystyle [aCB]\rightarrow [aE]}$
5. ${\displaystyle {\begin{cases}\ a[Da]\rightarrow [Da]a\\\ [aDB]\rightarrow [DaB]\\\ [Aa][Da]\rightarrow [ADa]a\\\ a[DaB]\rightarrow [Da][aB]\\\ [Aa][DaB]\rightarrow [ADa][aB]\end{cases}}}$
6. ${\displaystyle [ADa]\rightarrow [ACa]}$
7. ${\displaystyle {\begin{cases}\ a[Ea]\rightarrow [Ea]a\\\ [aE]\rightarrow [Ea]\\\ [Aa][Ea]\rightarrow [AEa]a\end{cases}}}$
8. ${\displaystyle [AEa]\rightarrow a}$

Kuroda normal form

Every context-sensitive grammar which does not generate the empty string can be transformed into a

This section needs additional citations for verification. Please help improve this article by adding citations to reliable sources in this section. Unsourced material may be challenged and removed. (August 2014) (Learn how and when to remove this template message)

Equivalence to linear bounded automaton

A formal language can be described by a context-sensitive grammar if and only if it is accepted by some linear bounded automaton (LBA).^[18] In some textbooks this result is attributed solely to Landweber and Kuroda.^[7] Others call it the Myhill–Landweber–Kuroda theorem.^[19] (Myhill introduced the concept of deterministic LBA in 1960. Peter S. Landweber published in 1963 that the language accepted by a deterministic LBA is context sensitive.^[20] Kuroda introduced the notion of non-deterministic LBA and the equivalence between LBA and CSGs in 1964.^[21][22])

As of 2010^{[update][needs update]} it is still an open question whether every context-sensitive language can be accepted by a deterministic LBA.^[23]

Closure properties

Context-sensitive languages are closed under complement. This 1988 result is known as the Immerman–Szelepcsényi theorem.^[19] Moreover, they are closed under

The decision problem that asks whether a certain string s belongs to the language of a given context-sensitive grammar G, is PSPACE-complete. Moreover, there are context-sensitive grammars whose languages are PSPACE-complete. In other words, there is a context-sensitive grammar G such that deciding whether a certain string s belongs to the language of G is PSPACE-complete (so G is fixed and only s is part of the input of the problem).^[26]

The

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

Notes