en>Download: /* Examples */cleanup and gen fixes using AWB

2014-12-01T08:06:22Z

Examples: cleanup and gen fixes using AWB

Show changes

en>Jochen Burghardt: moved ref.s to central ((cite doi)) template pages, where possible

2014-02-15T12:18:07Z

moved ref.s to central ((cite doi)) template pages, where possible

Show changes

en>David Eppstein: /* Computational properties */ supply requested citations

2014-01-23T01:45:58Z

Computational properties: supply requested citations

New page

In [[theoretical computer science]], a '''context-sensitive language''' is a [[formal language]] that can be defined by a [[context-sensitive grammar]]. That is one of the four types of grammars in the [[Chomsky hierarchy]].

== Computational properties ==

Computationally, a context-sensitive language is equivalent with a linear bounded [[nondeterministic Turing machine]], also called a [[linear bounded automaton]]. That is a non-deterministic Turing machine with a tape of only ''kn'' cells, where ''n'' is the size of the input and ''k'' is a constant associated with the machine. This means that every formal language that can be decided by such a machine is a context-sensitive language, and every context-sensitive language can be decided by such a machine.

This set of languages is also known as '''NLINSPACE''' or '''NSPACE'''(''O''(''n'')), because they can be accepted using linear space on a non-deterministic Turing machine.<ref>{{citation
| last = Rothe | first = Jörg
| isbn = 978-3-540-22147-0
| location = Berlin
| mr = 2164257
| page = 77
| publisher = Springer-Verlag
| series = Texts in Theoretical Computer Science. An EATCS Series
| title = Complexity theory and cryptology
| year = 2005}}.</ref> The class '''LINSPACE''' (or '''DSPACE'''(''O''(''n''))) is defined the same, except using a [[Deterministic automaton|deterministic]] Turing machine. Clearly '''LINSPACE''' is a subset of '''NLINSPACE''', but it is not known whether '''LINSPACE'''='''NLINSPACE'''.<ref>{{citation
| last = Odifreddi | first = P. G.
| isbn = 0-444-50205-X
| location = Amsterdam
| mr = 1718169
| page = 236
| publisher = North-Holland Publishing Co.
| series = Studies in Logic and the Foundations of Mathematics
| title = Classical recursion theory. Vol. II
| volume = 143
| year = 1999}}.</ref>

== Examples ==

One of the simplest context-sensitive languages is <math>L = \{ a^nb^nc^n : n \ge 1 \}</math>: the language of all strings consisting of ''n'' occurrences of the symbol "a", then ''n'' "b"'s, then ''n'' "c"'s (abc, aabbcc, 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]] |date=1983}}</ref> is defined as the set of all strings where "a", "b" and "c" (or any other set of three symbols) occurs equally often (aabccb, 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"]. ''NELS'', vol. 11, pp. 1–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>

Another example of a context-sensitive language that is not context-free is ''L'' = { ''a<sup>p</sup>'' : ''p'' is a [[prime number]] }. ''L'' can be shown to be a context-sensitive language by constructing a linear bounded automaton which accepts ''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 ''L''.

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.

== Properties of context-sensitive languages ==

* The union, intersection, concatenation and [[Kleene star]] of two context-sensitive languages is context-sensitive.<ref>{{cite book|authors=John E. Hopcroft, Jeffrey D. Ullman|title=Introduction to Automata Theory, Languages, and Computation|publisher=Addison-Wesley|year=1979}}; Exercise 9.10, p.230. In the 2003 edition, the chapter on CSL has been omitted.</ref>
* The complement of a context-sensitive language is itself context-sensitive<ref>{{cite journal | last = Immerman | first = Neil | year = 1988 | title =Nondeterministic space is closed under complementation | journal = SIAM J. Comput. | issue = 5 | pages = 935–938 | doi = 10.1137/0217058 | volume = 17 | url=http://www.cs.umass.edu/~immerman/pub/space.pdf }}</ref>
* Every [[context-free grammar|context-free]] language not containing the empty string is context-sensitive.<ref>(Hopcroft, Ullman, 1979); Theorem 9.9 b, p.228</ref>
* Membership of a string in a language defined by an arbitrary context-sensitive grammar, or by an arbitrary deterministic context-sensitive grammar, is a [[PSPACE-complete]] problem.

==See also==
* [[Linear bounded automaton]]
* [[Chomsky hierarchy]]
* [[Noncontracting grammar]]s – generate exactly the context-sensitive languages
* [[Indexed language]]s – a strict subset of the context-sensitive languages

==References==
{{reflist}}
* Sipser, M. (1996), ''Introduction to the Theory of Computation'', PWS Publishing Co.

{{Formal languages and grammars}}

{{DEFAULTSORT:Context-Sensitive Language}}
[[Category:Formal languages]]

Context-sensitive language - Revision history

en>Download: /* Examples */cleanup and gen fixes using AWB

en>Jochen Burghardt: moved ref.s to central ((cite doi)) template pages, where possible

en>David Eppstein: /* Computational properties */ supply requested citations