 Contextsensitive language

In theoretical computer science, a contextsensitive language is a formal language that can be defined by a contextsensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy. Of the four, this is the least often used, in both theory and practice.
Contents
Computational properties
Computationally, a contextsensitive language is equivalent with a linear bounded nondeterministic Turing machine, also called a linear bounded automaton. That is a nondeterministic 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 contextsensitive language, and every contextsensitive language can be decided by such a machine.
This set of languages is also known as NLINSPACE, because they can be accepted using linear space on a nondeterministic Turing machine. The class LINSPACE is defined the same, except using a deterministic Turing machine. Clearly LINSPACE is a subset of NLINSPACE, but it is not known whether LINSPACE=NLINSPACE. It is widely suspected they are not equal.
Examples
An example of a contextsensitive language that is not contextfree is L = { a^{p} : p is a prime number }. L can be shown to be a contextsensitive language by constructing a linear bounded automaton which accepts L. The language can easily be shown to be neither regular nor context free by applying the respective pumping lemmas for each of the language classes to L.
An example of recursive language that is not contextsensitive is any recursive language whose decision is an EXPSPACEhard problem, say, the set of pairs of equivalent regular expressions with exponentiation.
Properties of contextsensitive languages
 The union, intersection, and concatenation of two contextsensitive languages is contextsensitive.
 The complement of a contextsensitive language is itself contextsensitive.
 Every contextfree language is contextsensitive.
 Membership of a string in a language defined by an arbitrary contextsensitive grammar, or by an arbitrary deterministic contextsensitive grammar, is a PSPACEcomplete problem.
See also
 Linear bounded automaton
 Chomsky hierarchy
 Noncontracting grammars – generate exactly the contextsensitive languages
 Indexed languages – a strict subset of the contextsensitive languages
References
 Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
 Immerman, Neil (1988). "Nondeterministic space is closed under complementation". SIAM J. Comput. 17 (5): 935–938. doi:10.1137/0217058. http://www.cs.umass.edu/~immerman/pub/space.pdf.
Automata theory: formal languages and formal grammars Chomsky hierarchy Type0—Type1———Type2——Type3—Grammars (no common name)Linear contextfree rewriting systems etc.Treeadjoining etc.—Languages ContextsensitiveMinimal automaton Thread automataEach category of languages is a proper subset of the category directly above it.  Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it. Categories: Formal languages
Wikimedia Foundation. 2010.
Look at other dictionaries:
Mildly contextsensitive language — In formal grammar theory, mildly context sensitive languages are a class of formal languages which can be efficiently parsed, but still possess enough context sensitivity to allow the parsing of natural languages. The concept was first introduced … Wikipedia
Contextfree language — In formal language theory, a context free language is a language generated by some context free grammar. The set of all context free languages is identical to the set of languages accepted by pushdown automata. Contents 1 Examples 2 Closure… … Wikipedia
Contextsensitive — is an adjective meaning depending on context or depending on circumstances . It may refer to: Context sensitive grammar Context sensitive language Context sensitive help Context sensitive user interface in computing This disambiguation page lists … Wikipedia
Contextsensitive 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… … Wikipedia
Deterministic contextfree language — A deterministic context free language is a formal language which is defined by a deterministic context free grammar.[1] The set of deterministic context free languages is called DCFL[2] and is identical to the set of languages accepted by a… … Wikipedia
Contextfree grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… … Wikipedia
Indexed language — Indexed languages are a class of formal languages discovered by Alfred Aho [ cite journal  last = Aho  first = Alfred  year = 1968  title = Indexed grammars an extension of context free grammars  journal = Journal of the ACM  volume = 15 … … Wikipedia
List of formal language and literal string topics — This is a list of formal language and literal string topics, by Wikipedia page. Contents 1 Formal languages 2 Literal strings 3 Classical cryptography Formal languages Abstract syntax tree … Wikipedia
Bach language — In theoretical computer science, the Bach language is the formal language over an alphabet of three distinct symbols containing all strings in which the three symbols occur equally often. The Bach language is a context sensitive language. Pullum… … Wikipedia
Recursive language — This article is about a class of formal languages as they are studied in mathematics and theoretical computer science. For computer languages that allow a function to call itself recursively, see Recursion (computer science). In mathematics,… … Wikipedia