Editing Context-sensitive language (section)

== Examples ==
<!-- [[Bach language]] redirects here -->
One of the simplest context-sensitive but not context-free languages is <math>L = \{ a^nb^nc^n : n \ge 1 \}</math>: the language of all strings consisting of {{mvar|n}} occurrences of the symbol "a", then {{mvar|n}} "b"s, then {{mvar|n}} "c"s (abc, {{not a typo|aabbcc}}, {{not a typo|aaabbbccc}}, etc.). A superset of this language, called the Bach language,<ref>{{cite conference |last=Pullum |first=Geoffrey K. |year=1983 |title=Context-freeness and the computer processing of human languages |conference=Proc. 21st Annual Meeting of the [[Association for Computational Linguistics|ACL]] |url=http://www.aclweb.org/anthology/P83-1001}}</ref> is defined as the set of all strings where "a", "b" and "c" (or any other set of three symbols) occurs equally often ({{not a typo|aabccb}}, {{not a typo|baabcaccb}}, etc.) and is also context-sensitive.<ref>Bach, E. (1981). [http://people.umass.edu/ebach/papers/nels11.htm "Discontinuous constituents in generalized categorial grammars"] {{Webarchive|url=https://web.archive.org/web/20140121022931/http://people.umass.edu/ebach/papers/nels11.htm |date=2014-01-21 }}. ''NELS'', vol. 11, pp.&nbsp;1&ndash;12.</ref><ref>Joshi, A.; Vijay-Shanker, K.; and Weir, D. (1991). "The convergence of mildly context-sensitive grammar formalisms". In: Sells, P., Shieber, S.M. and Wasow, T. (Editors). ''Foundational Issues in Natural Language Processing''. Cambridge MA: Bradford.</ref>

{{mvar|L}} can be shown to be a context-sensitive language by constructing a linear bounded automaton which accepts {{mvar|L}}. The language can easily be shown to be neither [[regular language|regular]] nor [[context-free language|context-free]] by applying the respective [[pumping lemma]]s for each of the language classes to {{mvar|L}}.

Similarly:
 
<math>L_\textit{Cross} = \{ a^mb^nc^{m}d^{n} : m \ge 1, n \ge 1 \}</math> is another context-sensitive language; the corresponding context-sensitive grammar can be easily projected starting with two context-free grammars generating sentential forms in the formats
<math>a^mC^m</math>
and
<math>B^nd^n</math>
and then supplementing them with a permutation production like 
<math>CB\rightarrow BC</math>, a new starting symbol and standard syntactic sugar.

<math>L_{MUL3} = \{ a^mb^nc^{mn} : m \ge 1, n \ge 1 \}</math> is another context-sensitive language (the "3" in the name of this language is intended to mean a ternary alphabet); that is, the "product" operation defines a context-sensitive language (but the "sum" defines only a context-free language as the grammar <math>S\rightarrow aSc|R</math> and <math>R\rightarrow bRc|bc</math> shows). Because of the commutative property of the product, the most intuitive grammar for <math>L_\textit{MUL3}</math> is ambiguous. This problem can be avoided considering a somehow more restrictive definition of the language, e.g. <math>L_\textit{ORDMUL3} = \{ a^mb^nc^{mn} : 1 < m < n \}</math>. This can be specialized to 
<math>L_\textit{MUL1} = \{ a^{mn} : m > 1,  n > 1 \}</math> and, from this, to <math>L_{m^2} = \{ a^{m^2} : m > 1 \}</math>, <math>L_{m^3} = \{ a^{m^3} : m > 1 \}</math>, etc.

<math>L_{REP} = \{ w^{|w|} : w \in \Sigma^* \}</math> is a context-sensitive language. The corresponding context-sensitive grammar can be obtained as a generalization of the context-sensitive grammars for <math>L_\textit{Square} = \{ w^2 : w \in \Sigma^* \}</math>, <math>L_\textit{Cube} = \{ w^3 : w \in \Sigma^* \}</math>, etc.

<math>L_\textit{EXP} = \{ a^{2^n} : n \ge 1  \}</math> is a context-sensitive language.<ref>Example 9.5 (p. 224) of Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley</ref>

<math>L_\textit{PRIMES2} = \{ w : |w| \mbox { is prime }  \}</math> is a context-sensitive language (the "2" in the name of this language is intended to mean a binary alphabet). This was proved by Hartmanis using pumping lemmas for regular and context-free languages over a binary alphabet and, after that, sketching a linear bounded multitape automaton accepting <math>L_{PRIMES2}</math>.<ref>{{cite journal | doi=10.1145/321466.321470 | url=https://ecommons.cornell.edu/bitstream/1813/5864/1/68-1.pdf | author=J. Hartmanis and H. Shank | title=On the Recognition of Primes by Automata | journal=[[Journal of the ACM]] | volume=15 | number=3 | pages=382–389 | date=Jul 1968 | hdl=1813/5864 | s2cid=17998039 | hdl-access=free }}</ref>

<math>L_\textit{PRIMES1} = \{ a^p : p \mbox { is prime }  \}</math> is a context-sensitive language (the "1" in the name of this language is intended to mean a unary alphabet). This was credited by A. Salomaa to Matti Soittola by means of a linear bounded automaton over a unary alphabet<ref>Salomaa, Arto (1969), ''Theory of Automata'', {{ISBN|978-0-08-013376-8}}, Pergamon, 276 pages. {{doi|10.1016/C2013-0-02221-9}}</ref> (pages 213–214, exercise 6.8) and also to Marti Penttonen by means of a context-sensitive grammar also over a unary alphabet (See: Formal Languages by A. Salomaa, page 14, Example 2.5).

An example of [[recursive language]] that is not context-sensitive is any recursive language whose decision is an [[EXPSPACE]]-hard problem, say, the set of pairs of equivalent [[regular expression]]s with exponentiation.