Context-sensitive language

"Context-dependent" redirects here. For the type of memory, see Context-dependent memory.

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 known as type-1 in the Chomsky hierarchy of formal languages.

Computational properties

Computationally, a context-sensitive language is equivalent to 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 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 context-sensitive.^[4][5]

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 nor context-free by applying the respective pumping lemmas for each of the language classes to L.

Similarly:

${\displaystyle L_{\textit {Cross}}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}}$ 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 ${\displaystyle a^{m}C^{m}}$ and ${\displaystyle B^{n}d^{n}}$ and then supplementing them with a permutation production like ${\displaystyle CB\rightarrow BC}$, a new starting symbol and standard syntactic sugar.

${\displaystyle L_{MUL3}=\{a^{m}b^{n}c^{mn}:m\geq 1,n\geq 1\}}$ 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 ${\displaystyle S\rightarrow aSc|R}$ and ${\displaystyle R\rightarrow bRc|bc}$ shows). Because of the commutative property of the product, the most intuitive grammar for ${\displaystyle L_{\textit {MUL3}}}$ is ambiguous. This problem can be avoided considering a somehow more restrictive definition of the language, e.g. ${\displaystyle L_{\textit {ORDMUL3}}=\{a^{m}b^{n}c^{mn}:1<m<n\}}$. This can be specialized to ${\displaystyle L_{\textit {MUL1}}=\{a^{mn}:m>1,n>1\}}$ and, from this, to ${\displaystyle L_{m^{2}}=\{a^{m^{2}}:m>1\}}$, ${\displaystyle L_{m^{3}}=\{a^{m^{3}}:m>1\}}$, etc.

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

${\displaystyle L_{\textit {EXP}}=\{a^{2^{n}}:n\geq 1\}}$ is a context-sensitive language.^[6]

${\displaystyle L_{\textit {PRIMES2}}=\{w:|w|{\mbox{ is prime }}\}}$ 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 ${\displaystyle L_{PRIMES2}}$.^[7]

${\displaystyle L_{\textit {PRIMES1}}=\{a^{p}:p{\mbox{ is prime }}\}}$ 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^[8] (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 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.^[9]
• The complement of a context-sensitive language is itself context-sensitive^[10] 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.

See also

• Linear bounded automaton
• List of parser generators for context-sensitive languages
• Chomsky hierarchy
• Indexed languages – a strict subset of the context-sensitive languages
• Weir hierarchy