Editing Context-sensitive grammar (section)

{{Short description|Type of a formal grammar}}
A '''context-sensitive grammar''' ('''CSG''') is a [[formal grammar]] in which the left-hand sides and right-hand sides of any [[Production (computer science)|production rules]] may be surrounded by a context of [[terminal symbol|terminal]] and [[nonterminal symbol]]s. Context-sensitive grammars are more general than [[context-free grammar]]s, 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 grammar]]s. Thus, CSGs are positioned between context-free and unrestricted grammars in the [[Chomsky hierarchy]].<ref>(Hopcroft, Ullman, 1979); Sect.9.4, p.227</ref>

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,<ref name="Linz2011">{{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}}</ref><ref name="Meduna2000">{{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}}</ref><ref name="DavisSigal1994">{{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}}</ref><ref>{{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}}</ref> although this is not how [[Noam Chomsky]] defined them in 1959.<ref name="Levelt2008">{{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}}</ref><ref name="DavisSigal1994b">{{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}}</ref> This choice of definition makes no difference in terms of the languages generated (i.e. the two definitions are [[weak equivalence (formal languages)|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.<ref>{{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}}</ref><ref name="Levelt2008-126">{{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}}</ref>

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]].<ref name="Vide1999">{{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}}</ref>

Although it is well known that certain features of languages (e.g. [[cross-serial dependency]]) are not context-free, it is an [[open problem|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 language]]s.{{citation needed|date=March 2018}} The syntaxes of some [[visual programming language]]s can be described by context-sensitive [[graph grammar]]s.<ref>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.</ref>