Subject: Contextsensitive language 
Author:
Heden

[
Next Thread 
Previous Thread 
Next Message 
Previous Message
]
Date Posted: 06:08:32 01/22/16 Fri
Author Host/IP: NoHost/121.54.54.139
Contextsensitive language
From Wikipedia, the free encyclopedia
"Contextdependent" redirects here. For the type of memory, see Contextdependent memory.
In theoretical computer science, a contextsensitive language is a formal language that can be defined by a contextsensitive grammar (and equivalently by a noncontracting grammar). That is one of the four types of grammars in the Chomsky hierarchy.
Contents [hide]
1 Computational properties
2 Examples
3 Properties of contextsensitive languages
4 See also
5 References
Computational properties[edit]
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 or NSPACE(O(n)), because they can be accepted using linear space on a nondeterministic Turing machine.[1] The class LINSPACE (or DSPACE(O(n))) 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.[2]
Examples[edit]
One of the simplest contextsensitive, but not contextfree languages is L = \{ a^nb^nc^n : n \ge 1 \}: 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,[3] 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 contextsensitive.[4][5]
Another example of a contextsensitive language that is not contextfree is L = { ap : 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[edit]
The union, intersection, concatenation of two contextsensitive languages is contextsensitive; the Kleene plus of a contextsensitive language is contextsensitive.[6]
The complement of a contextsensitive language is itself contextsensitive[7] a result known as the Immerman–Szelepcsényi theorem.
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[edit]
Linear bounded automaton
Chomsky hierarchy
Indexed languages – a strict subset of the contextsensitive languages
Weir hierarchy
References[edit]
Jump up ^ Rothe, Jörg (2005), Complexity theory and cryptology, Texts in Theoretical Computer Science. An EATCS Series, Berlin: SpringerVerlag, p. 77, ISBN 9783540221470, MR 2164257.
Jump up ^ Odifreddi, P. G. (1999), Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics 143, Amsterdam: NorthHolland Publishing Co., p. 236, ISBN 044450205X, MR 1718169.
Jump up ^ Pullum, Geoffrey K. (1983). Contextfreeness and the computer processing of human languages. Proc. 21st Annual Meeting of the ACL.
Jump up ^ Bach, E. (1981). "Discontinuous constituents in generalized categorial grammars". NELS, vol. 11, pp. 1–12.
Jump up ^ Joshi, A.; VijayShanker, K.; and Weir, D. (1991). "The convergence of mildly contextsensitive grammar formalisms". In: Sells, P., Shieber, S.M. and Wasow, T. (Editors). Foundational Issues in Natural Language Processing. Cambridge MA: Bradford.
Jump up ^ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. AddisonWesley.; Exercise 9.10, p.230. In the 2003 edition, the chapter on contextsensitive languages has been omitted.
Jump up ^ Immerman, Neil (1988). "Nondeterministic space is closed under complementation" (PDF). SIAM J. Comput. 17 (5): 935–938. doi:10.1137/0217058.
Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
[hide] v t e
Automata theory: formal languages and formal grammars
Chomsky hierarchy Grammars Languages Abstract machines
Type0
—
Type1
—
—
—
—
—
Type2
—
—
Type3
—
—
Unrestricted
(no common name)
Contextsensitive
Positive range concatenation
Indexed
—
Linear contextfree rewriting systems
Treeadjoining
Contextfree
Deterministic contextfree
Visibly pushdown
Regular
—
Nonrecursive
Recursively enumerable
Decidable
Contextsensitive
Positive range concatenation*
Indexed*
—
Linear contextfree rewriting language
Treeadjoining
Contextfree
Deterministic contextfree
Visibly pushdown
Regular
Starfree
Finite
Turing machine
Decider
Linearbounded
PTIME Turing Machine
Nested stack
Thread automaton
—
Embedded pushdown
Nondeterministic pushdown
Deterministic pushdown
Visibly pushdown
Finite
Counterfree (with aperiodic finite monoid)
Acyclic finite
Each category of languages, except those marked by a *, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.
Categories: Formal languages
[
Next Thread 
Previous Thread 
Next Message 
Previous Message
]
 