context-sensitive language


A context-sensitive language is a languagePlanetmathPlanetmath over some alphabet generated by generated by some known as a context-sensitive grammar.

Formally, a context-sensitive language is a formal grammar G=(Σ,N,P,σ), such that given any production in P, it

  1. 1.

    either has the form

    uXvuwv,

    where XN, u,v,wΣ*, and wλ, the empty wordPlanetmathPlanetmathPlanetmath,

  2. 2.

    or is σλ, provided that the start symbol σ does not occur on the right side of any productions in P.

In other words, if G does not contain the production σλ, then any production will have the form in condition 1. On the other hand, if G does contain σλ, then for any production uXvuwv of G, σ does not occur in uwv.

The reason for including the second condition is to ensure the possibility that λ may be generated by the grammar.

One may interpret the first condition as follows: the non-terminal symbol X can only be transformed into the word w if it is surrounded by u and v, or that it is in the “context” of uXv. If in each production uXvuwv of G, u=v=λ, (so that X no longer has a “context”), then G is a context-free grammar.

Given a context-sensitive grammar G, the context-sensitive language generated by G is L(G). In other words,

L(G):={vT*σ*v},

where T=Σ-N is the set of terminals, and σ*v means that the word v over Σ is produced after a finite number of applications of the productions in P to σ.

With condition 2, we see that a context-sensitive language contains λ iff it is generated by a context-sensitive grammar containing σλ. With condition 2, every context-free language is context-sensitive. Without condition 2, every λ-free context-free language is λ-free context-sensitive.

{anbncnn0} and {a2nn0} are examples of context-sensitive languages that are not context-free, the second of which is λ-free.

Remarks.

  1. 1.

    A formal grammar G is said to be length-increasing if for every production UV of G, the length of U is at most the length of V: |U||V|. Every context-sensitive grammar not containing σλ (condition 2) is length-increasing. Conversely, any language generated by a length-increasing grammar is context-sensitive.

  2. 2.

    The minimal automaton required for processing a context-sensitive languages is a bounded non-deterministic Turing machine (bounded linear automaton).

  3. 3.

    The family of context-sensitive languages has the following closure properties: union, intersectionMathworldPlanetmath, concatenationMathworldPlanetmath, Kleene star, reversal, and complementation (proved in 1988). It is not closed under homomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath.

  4. 4.

    In the Chomsky hierarchy, context-sensitive grammars are at Level 1. In fact, every context-sensitive language is recursive. The converse is not true, however.

  5. 5.

    Given a context-sensitive language L and a word w, it is decidable whether wL.

References

  • 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
  • 2 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their RelationMathworldPlanetmathPlanetmath to Automata, Addison-Wesley, (1969).
Title context-sensitive language
Canonical name ContextsensitiveLanguage
Date of creation 2013-03-22 16:28:40
Last modified on 2013-03-22 16:28:40
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 23
Author CWoo (3771)
Entry type Definition
Classification msc 68Q42
Classification msc 68Q45
Synonym type-1 language
Synonym type-1 grammar
Related topic ContextFreeLanguage
Related topic LinearBoundedAutomaton
Defines context-sensitive grammar
Defines context-sensitive
Defines length-increasing