Context-sensitive language
Encyclopedia
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
. Of the four, this is the least often used, in both theory and practice.
. 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 NLIN-SPACE, because they can be accepted using linear space on a non-deterministic Turing machine. The class LIN-SPACE is defined the same, except using a deterministic
Turing machine. Clearly LIN-SPACE is a subset of NLIN-SPACE, but it is not known whether LIN-SPACE=NLIN-SPACE. It is widely suspected they are not equal.
}. 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 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.
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, a context-sensitive language is a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
that can be defined by a context-sensitive grammar
Context-sensitive grammar
A context-sensitive grammar 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...
. That is one of the four types of grammars in the Chomsky hierarchy
Chomsky hierarchy
Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy is a containment hierarchy of classes of formal grammars....
. Of the four, this is the least often used, in both theory and practice.
Computational properties
Computationally, a context-sensitive language is equivalent with a linear bounded nondeterministic Turing machine, also called a linear bounded automatonLinear bounded automaton
In computer science, a linear bounded automaton is a restricted form of nondeterministic Turing machine.-Operation:Linear bounded automata satisfy the following three conditions:...
. 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 NLIN-SPACE, because they can be accepted using linear space on a non-deterministic Turing machine. The class LIN-SPACE is defined the same, except using a deterministic
Deterministic automaton
Deterministic automaton is a concept of automata theory in which the outcome of a transition from one state to another given a certain input can be predicted for every occurrence....
Turing machine. Clearly LIN-SPACE is a subset of NLIN-SPACE, but it is not known whether LIN-SPACE=NLIN-SPACE. It is widely suspected they are not equal.
Examples
An example of a context-sensitive language that is not context-free is L = { ap : p is a prime numberPrime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
}. 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
Regular language
In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using regular expression....
nor context free
Context-free 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.-Examples:...
by applying the respective pumping lemma
Pumping lemma
In the theory of formal languages in computability theory, a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of...
s for each of the language classes to L.
An example of recursive language
Recursive language
In mathematics, logic and computer science, a formal language is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language...
that is not context-sensitive is any recursive language whose decision is an EXPSPACE
EXPSPACE
In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O space, where p is a polynomial function of n...
-hard problem, say, the set of pairs of equivalent regular expression
Regular expression
In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...
s with exponentiation.
Properties of context-sensitive languages
- The union, intersection, and concatenation of two context-sensitive languages is context-sensitive.
- The complement of a context-sensitive language is itself context-sensitive.
- Every context-freeContext-free grammarIn formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....
language is context-sensitive. - 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-completePSPACE-completeIn complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
problem.
See also
- Linear bounded automatonLinear bounded automatonIn computer science, a linear bounded automaton is a restricted form of nondeterministic Turing machine.-Operation:Linear bounded automata satisfy the following three conditions:...
- Chomsky hierarchyChomsky hierarchyWithin the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy is a containment hierarchy of classes of formal grammars....
- Noncontracting grammarNoncontracting grammar- Formal definition :In formal language theory, a grammar is noncontracting if all of its production rules are of the formThat is, none of the rules decreases the size of the string that is being rewritten....
s – generate exactly the context-sensitive languages - Indexed languageIndexed languageIndexed languages are a class of formal languages discovered by Alfred Aho; they are described by indexed grammars and can be recognized by nested stack automatons....
s – a strict subset of the context-sensitive languages