Context-sensitive language

(Redirected from Context sensitive language)

In formal language theory, a context-sensitive language is a language that can be defined by a context-sensitive grammar (and equivalently by a noncontracting grammar). Context-sensitive 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 ${\displaystyle kn}$ cells, where ${\displaystyle n}$ is the size of the input and ${\displaystyle 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.[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

One of the simplest context-sensitive but not context-free languages is ${\displaystyle L=\{a^{n}b^{n}c^{n}:n\geq 1\}}$: the language of all strings consisting of ${\displaystyle n}$ occurrences of the symbol "a", then ${\displaystyle n}$ "b"'s, then ${\displaystyle 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 context-sensitive.[4][5]

${\displaystyle L}$ can be shown to be a context-sensitive language by constructing a linear bounded automaton which accepts ${\displaystyle 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 ${\displaystyle 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 expressions with exponentiation.

Properties of context-sensitive languages

• The union, intersection, concatenation of two context-sensitive languages is context-sensitive, also the Kleene plus of a context-sensitive language is context-sensitive.[6]
• The complement of a context-sensitive language is itself context-sensitive[7] a result known as the Immerman–Szelepcsényi theorem.
• 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.

References

1. ^ Rothe, Jörg (2005), Complexity theory and cryptology, Texts in Theoretical Computer Science. An EATCS Series, Berlin: Springer-Verlag, p. 77, ISBN 978-3-540-22147-0, MR 2164257.
2. ^ Odifreddi, P. G. (1999), Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, 143, Amsterdam: North-Holland Publishing Co., p. 236, ISBN 0-444-50205-X, MR 1718169.
3. ^ Pullum, Geoffrey K. (1983). Context-freeness and the computer processing of human languages. Proc. 21st Annual Meeting of the ACL.
4. ^ Bach, E. (1981). "Discontinuous constituents in generalized categorial grammars". NELS, vol. 11, pp. 1–12.
5. ^ 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.
6. ^ John E. Hopcroft; Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.; Exercise 9.10, p.230. In the 2000 edition, the chapter on context-sensitive languages has been omitted.
7. ^ 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.