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. 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.(Hopcroft, Ullman, 1979); Sect.9.4, p.227

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,{{cite book|first=Peter|last=Linz|title=An Introduction to Formal Languages and Automata|url=https://books.google.com/books?id=hsxDiWvVdBcC&pg=PA291|year=2011|publisher=Jones & Bartlett Publishers|isbn=978-1-4496-1552-9|page=291}}{{cite book|first=Alexander|last=Meduna|author-link=Alexander Meduna|title=Automata and Languages: Theory and Applications|url=https://books.google.com/books?id=s7gEErax71cC&pg=PA730|year=2000|publisher=Springer Science & Business Media|isbn=978-1-85233-074-3|page=730}}{{cite book|first1=Martin|last1=Davis|author-link1=Martin Davis (mathematician)|first2=Ron|last2=Sigal|first3=Elaine J.|last3=Weyuker|author-link3=Elaine Weyuker|title=Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science|url=https://books.google.com/books?id=dSHIIx0uGx0C&pg=PA189|year=1994|publisher=Morgan Kaufmann|isbn=978-0-08-050246-5|page=189|edition=2nd}}{{cite book|last=Martin|first=John C.|title=Introduction to Languages and the Theory of Computation|year=2010|publisher=McGraw-Hill|location=New York, NY|isbn=9780073191461|edition=4th|page=277}} although this is not how Noam Chomsky defined them in 1959.{{cite book|first=Willem J. M.|last=Levelt|author-link=Willem Levelt|title=An Introduction to the Theory of Formal Languages and Automata|url=https://books.google.com/books?id=tFvtwGYNe7kC&pg=PA26|year=2008|publisher=John Benjamins Publishing|isbn=978-90-272-3250-2|page=26}}{{cite book|first1=Martin|last1=Davis|author-link1=Martin Davis (mathematician)|first2=Ron |last2=Sigal|first3=Elaine J.|last3=Weyuker|author-link3=Elaine Weyuker|title=Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science|url=https://books.google.com/books?id=dSHIIx0uGx0C&pg=PA330|year=1994|publisher=Morgan Kaufmann|isbn=978-0-08-050246-5|pages=330–331|edition=2nd}} 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.{{cite book |last=Chomsky |first=N. |author-link=Noam Chomsky|year=1963|chapter=Formal properties of grammar|title=Handbook of Mathematical Psychology|editor1-first=R. D.|editor1-last=Luce|editor2-first=R. R.|editor2-last=Bush|editor3-first=E.|editor3-last=Galanter|location=New York|publisher=Wiley|pages=360–363|chapter-url=https://archive.org/details/handbookofmathem017893mbp}}{{cite book|first=Willem J. M.|last=Levelt|author-link=Willem Levelt|title=An Introduction to the Theory of Formal Languages and Automata|url=https://books.google.com/books?id=tFvtwGYNe7kC&pg=PA125|year=2008|publisher=John Benjamins Publishing|isbn=978-90-272-3250-2|pages=125–126}}

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.{{cite book|editor=Carlos Martín Vide|title=Issues in Mathematical Linguistics: Workshop on Mathematical Linguistics, State College, Pa., April 1998|url=https://books.google.com/books?id=BW2QNSvH2CoC&pg=PA186|year=1999|publisher=John Benjamins Publishing|isbn=90-272-1556-1|pages=186–187}}

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.{{citation needed|date=March 2018}} The syntaxes of some visual programming languages can be described by context-sensitive graph grammars.Zhang, Da-Qian, Kang Zhang, and Jiannong Cao. "[https://web.archive.org/web/20180323220143/https://pdfs.semanticscholar.org/5d3d/217d73e0f6bbeefa3749c16fbc7b2e00ec0b.pdf A context-sensitive graph grammar formalism for the specification of visual languages]." The Computer Journal 44.3 (2001): 186–200.

Formal definition

= Formal grammar =

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).

= Context-sensitive grammar =

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

: αAβ → αγβ

with A ∈ N,i.e., A a single nonterminal $\alpha, \beta\in (N \cup \Sigma \setminus\{S\})^*$ ,i.e., α and β strings of nonterminals (except for the start symbol) and terminals and $\gamma\in (N \cup \Sigma \setminus\{S\})^+$ .i.e., γ is a nonempty string of nonterminals (except for the start symbol) 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.

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.

= (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 weakly equivalent.{{cite book |last1=Hopcroft |first1=John E. |url=https://archive.org/details/introductiontoau00hopc |title=Introduction to Automata Theory, Languages, and Computation |last2=Ullman |first2=Jeffrey D. |publisher=Addison-Wesley |year=1979 |isbn=9780201029888 |author-link1=John Hopcroft |author-link2=Jeffrey Ullman |url-access=registration}}; p. 223–224; Exercise 9, p. 230. In the 2003 edition, the chapter on CSGs has been omitted.

Some authors use the term context-sensitive grammar to refer to noncontracting grammars in general.

The left-context- and right-context-sensitive grammars are defined by restricting the rules to just the form αA → αγ and to just Aβ → γβ, respectively. The languages generated by these grammars are also the full class of context-sensitive languages.{{cite book |last=Hazewinkel |first=Michiel |url=https://books.google.com/books?id=s9F71NJxwzoC&pg=PA297 |title=Encyclopaedia of Mathematics |publisher=Springer Science & Business Media |year=1989 |isbn=978-1-55608-003-6 |volume=4 |page=297 |author-link=Michiel Hazewinkel}} also at https://www.encyclopediaofmath.org/index.php/Grammar,_context-sensitive The equivalence was established by Penttonen normal form.{{cite book |last1=Ito |first1=Masami |url=https://books.google.com/books?id=xuaR2bJq0rcC&pg=PA183 |title=Automata, Formal Languages and Algebraic Systems: Proceedings of AFLAS 2008, Kyoto, Japan, 20–22 September 2008 |last2=Kobayashi |first2=Yūji |last3=Shoji |first3=Kunitaka |publisher=World Scientific |year=2010 |isbn=978-981-4317-60-3 |page=183}} citing {{Cite journal |last1=Penttonen |first1=Martti |date=Aug 1974 |title=One-sided and two-sided context in formal grammars |journal=Information and Control |volume=25 |issue=4 |pages=371–392 |doi=10.1016/S0019-9958(74)91049-3 |doi-access=free}}

Examples

= ''anbncn'' =

The following context-sensitive grammar, with start symbol S, generates the canonical non-context-free language { aⁿbⁿcⁿ | n ≥ 1 } :{{cn|date=January 2022}}

1.		S	→	a	B	C
2.		S	→	a	S	B	C
3.	C	B	→	C	Z
4.	C	Z	→	W	Z
5.	W	Z	→	W	C
6.	W	C	→	B	C
7.	a	B	→	a	b
8.	b	B	→	b	b \|
9.	b	C	→	b	c
10.	c	C	→	c	c

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 (four rules are needed for that since a rule CB → BC wouldn't fit into the scheme αAβ → αγβ); rules 7–10 allow replacing a non-terminal B or C with its corresponding terminal b or c, respectively, provided it is in the right place.

A generation chain for {{not a typo|aaabbbccc}} is:

: S

: →₂ {{not a typo|aSBC}}

: →₂ {{not a typo|aaSBCBC}}

: →₁ {{not a typo|aaaBCBCBC}}

: →₃ {{not a typo|aaaBCZCBC}}

: →₄ {{not a typo|aaaBWZCBC}}

: →₅ {{not a typo|aaaBWCCBC}}

: →₆ {{not a typo|aaaBBCCBC}}

: →₃ {{not a typo|aaaBBCCZC}}

: →₄ {{not a typo|aaaBBCWZC}}

: →₅ {{not a typo|aaaBBCWCC}}

: →₆ {{not a typo|aaaBBCBCC}}

: →₃ {{not a typo|aaaBBCZCC}}

: →₄ {{not a typo|aaaBBWZCC}}

: →₅ {{not a typo|aaaBBWCCC}}

: →₆ {{not a typo|aaaBBBCCC}}

: →₇ {{not a typo|aaabBBCCC}}

: →₈ {{not a typo|aaabbBCCC}}

: →₈ {{not a typo|aaabbbCCC}}

: →₉ {{not a typo|aaabbbcCC}}

: →₁₀ {{not a typo|aaabbbccC}}

: →₁₀ {{not a typo|aaabbbccc}}

= ''anbncndn'', 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:{{cn|date=January 2022}}

Start with a kernel of regular productions generating the sentential forms

$(ABCD)^{n}abcd$ and then include the non contracting productions

$p_{Da} : Da\rightarrow aD$ ,

$p_{Db} : Db\rightarrow bD$ ,

$p_{Dc} : Dc\rightarrow cD$ ,

$p_{Dd} : Dd\rightarrow dd$ ,

$p_{Ca} : Ca\rightarrow aC$ ,

$p_{Cb} : Cb\rightarrow bC$ ,

$p_{Cc} : Cc\rightarrow cc$ ,

$p_{Ba} : Ba\rightarrow aB$ ,

$p_{Bb} : Bb\rightarrow bb$ ,

$p_{Aa} : Aa\rightarrow aa$ .

= ''ambncmdn'' =

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$ .{{citation needed|date=November 2018}}

= ''a''2''i'' =

A noncontracting grammar for the language { a^2ⁱ | i ≥ 1 } is constructed in Example 9.5 (p. 224) of (Hopcroft, Ullman, 1979):They obtained the grammar by systematic transformation of an unrestricted grammar, given in Exm. 9.4, viz.:

$S\rightarrow ACaB$ ,
$Ca\rightarrow aaC$ ,
$CB\rightarrow DB$ ,
$CB\rightarrow E$ ,
$aD\rightarrow Da$ ,
$AD\rightarrow AC$ ,
$aE\rightarrow Ea$ ,
$AE\rightarrow \varepsilon$ .

In the context-sensitive grammar, a string enclosed in square brackets, like $[ACaB]$ , is considered a single symbol (similar to e.g. in Backus–Naur form). The symbol names are chosen to resemble the unrestricted grammar. Likewise, rule groups in the context-sensitive grammar are numbered by the unrestricted-grammar rule they originated from.

$S\rightarrow [ACaB]$
$\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}

$[aCB]\rightarrow [aDB]$
$[aCB]\rightarrow [aE]$
$\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}

$[ADa]\rightarrow [ACa]$
$\begin{cases}$

\ a[Ea]\rightarrow [Ea]a \\ \ [aE]\rightarrow [Ea] \\ \ [Aa][Ea]\rightarrow [AEa]a \end{cases}

$[AEa]\rightarrow a$

Kuroda normal form

Every context-sensitive grammar which does not generate the empty string can be transformed into a weakly equivalent one in Kuroda normal form. "Weakly equivalent" here means that the two grammars generate the same language. The normal form will not in general be context-sensitive, but will be a noncontracting grammar.{{cite journal | first=Sige-Yuki | last=Kuroda | author-link=S.-Y. Kuroda | title=Classes of languages and linear-bounded automata | journal=Information and Control | volume=7 | number=2 | pages=207–223 | date=June 1964 | doi=10.1016/s0019-9958(64)90120-2| doi-access=free }}{{cite book |last1=Mateescu | first1=Alexandru |last2=Salomaa|first2=Arto |author-link2=Arto Salomaa|editor1-first=Grzegorz| editor1-last=Rozenberg|editor-link1=Grzegorz Rozenberg |editor2-first=Arto| editor2-last=Salomaa |editor-link2=Arto Salomaa|title=Handbook of Formal Languages. Volume I: Word, language, grammar |publisher=Springer-Verlag |year=1997 |pages=175–252 |chapter=Chapter 4: Aspects of Classical Language Theory |isbn=3-540-61486-9}}, Here: Theorem 2.2, p. 190

The Kuroda normal form is an actual normal form for non-contracting grammars.

Properties and uses

= 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).(Hopcroft, Ullman, 1979); Theorem 9.5, 9.6, p. 225–226 In some textbooks this result is attributed solely to Landweber and Kuroda. Others call it the Myhill–Landweber–Kuroda theorem.{{Cite web |first=Klaus |last=Sutner |url=https://www.cs.cmu.edu/~flac/pdf/ContSens.pdf |title=Context Sensitive Grammars |publisher=Carnegie Mellon University |date=Spring 2016 |access-date=2019-08-29 |archive-date=2017-02-03 |archive-url=https://web.archive.org/web/20170203081505/http://www.cs.cmu.edu/~flac/pdf/ContSens.pdf |url-status=dead }} (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.{{cite journal | author=P.S. Landweber | title=Three Theorems on Phrase Structure Grammars of Type 1 | journal=Information and Control | volume=6 | number=2 | pages=131–136 | year=1963 |doi=10.1016/s0019-9958(63)90169-4 | doi-access=free }} Kuroda introduced the notion of non-deterministic LBA and the equivalence between LBA and CSGs in 1964.{{cite book|first=Alexander|last=Meduna|author-link=Alexander Meduna|title=Automata and Languages: Theory and Applications|url=https://books.google.com/books?id=s7gEErax71cC&pg=PA755|year=2000|publisher=Springer Science & Business Media|isbn=978-1-85233-074-3|page=755}}{{cite book|first=Willem J. M.|last=Levelt|author-link=Willem Levelt|title=An Introduction to the Theory of Formal Languages and Automata|url=https://books.google.com/books?id=tFvtwGYNe7kC&pg=PA126|year=2008|publisher=John Benjamins Publishing|isbn=978-90-272-3250-2|pages=126–127}})

{{As of|2010}}{{update inline|date=May 2023}} it is still an open question whether every context-sensitive language can be accepted by a deterministic LBA.{{cite book|last=Martin|first=John C.|title=Introduction to Languages and the Theory of Computation|year=2010|publisher=McGraw-Hill|location=New York, NY|isbn=9780073191461|edition=4th|page=283}}

= Closure properties =

Context-sensitive languages are closed under complement. This 1988 result is known as the Immerman–Szelepcsényi theorem.

Moreover, they are closed under union, intersection, concatenation, substitution,more formally: if L ⊆ Σ^* is a context-sensitive language and f maps each a∈Σ to a context-sensitive language f(a), the f(L) is again a context-sensitive language inverse homomorphism, and Kleene plus.(Hopcroft, Ullman, 1979); Exercise S9.10, p. 230–231

Every recursively enumerable language L can be written as h(L) for some context-sensitive language L and some string homomorphism h.(Hopcroft, Ullman, 1979); Exercise S9.14, p. 230–232. h maps each symbol to itself or to the empty string.

= Computational problems =

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).An example of such a grammar, designed to solve the QSAT problem, is given in {{Cite book|last=Lita|first=C. V.|title=2016 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC) |chapter=On Complexity of the Detection Problem for Bounded Length Polymorphic Viruses |date=2016-09-01|pages=371–378|doi=10.1109/SYNASC.2016.064|isbn=978-1-5090-5707-8|s2cid=18067130}}

The emptiness problem for context-sensitive grammars (given a context-sensitive grammar G, is L(G)=∅ ?) is undecidable.(Hopcroft, Ullman, 1979); Exercise S9.13, p. 230–231This also follows from (1) context-free languages being also context-sensitive, (2) context-sensitive language being closed under intersection, but (3) disjointness of context-free languages being undecidable.

= As model of natural languages =

Savitch has proven the following theoretical result, on which he bases his criticism of CSGs as basis for natural language: for any recursively enumerable set R, there exists a context-sensitive language/grammar G which can be used as a sort of proxy to test membership in R in the following way: given a string s, s is in R if and only if there exists a positive integer n for which scⁿ is in G, where c is an arbitrary symbol not part of R.

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.{{citation needed|date=November 2011}} 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.{{cn|date=December 2022}} 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ⁿbⁿcⁿdⁿ | n ≥ 1} for example.{{cite web|url=http://user.phil-fak.uni-duesseldorf.de/~kallmeyer/GrammarFormalisms/4nl-cfg.pdf |archive-url=https://web.archive.org/web/20140819085139/http://user.phil-fak.uni-duesseldorf.de/~kallmeyer/GrammarFormalisms/4nl-cfg.pdf |archive-date=2014-08-19 |url-status=live|title=Mildly Context-Sensitive Grammar Formalisms: Natural Languages are not Context-Free|first=Laura|last=Kallmeyer|year=2011}}{{cite web|url=http://user.phil-fak.uni-duesseldorf.de/~kallmeyer/GrammarFormalisms/4lcfrs-intro.pdf |archive-url=https://web.archive.org/web/20140819085928/http://user.phil-fak.uni-duesseldorf.de/~kallmeyer/GrammarFormalisms/4lcfrs-intro.pdf |archive-date=2014-08-19 |url-status=live|title=Mildly Context-Sensitive Grammar Formalisms: Linear Context-Free Rewriting Systems|first=Laura|last=Kallmeyer|year=2011}}{{cite book|first=Laura|last=Kallmeyer|title=Parsing Beyond Context-Free Grammars|year=2010|publisher=Springer Science & Business Media|isbn=978-3-642-14846-0|pages=1–5}}

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.

Notes

References

External links

[https://web.archive.org/web/20110708224600/https://danielmattosroberts.com/earley/context-sensitive-earley.pdf Earley Parsing for Context-Sensitive Grammars]

Category:Formal languages

Category:Grammar frameworks