Editing Context-sensitive grammar (section)

=== 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).<ref>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}}</ref>

The [[emptiness problem]] for context-sensitive grammars (given a context-sensitive grammar ''G'', is ''L''(''G'')=∅ ?) is [[Undecidable language|undecidable]].<ref>(Hopcroft, Ullman, 1979); Exercise S9.13, p.&nbsp;230–231</ref><ref group=note>This also follows from (1) [[#top|context-free languages being also context-sensitive]], (2) [[#Closure properties|context-sensitive language being closed under intersection]], but (3) [[Context-free grammar#Language disjointness|disjointness of context-free languages being undecidable]].</ref>