## You are here

Homecontext-sensitive language

## Primary tabs

# context-sensitive language

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

Formally, a *context-sensitive language* is a formal grammar $G=(\Sigma,N,P,\sigma)$, such that given any production in $P$, it

1. either has the form

$uXv\to uwv,$ where $X\in N$, $u,v,w\in\Sigma^{*}$, and $w\neq\lambda$, the empty word,

2. or is $\sigma\to\lambda$, provided that the start symbol $\sigma$ does not occur on the right side of any productions in $P$.

In other words, if $G$ does not contain the production $\sigma\to\lambda$, then any production will have the form in condition 1. On the other hand, if $G$ does contain $\sigma\to\lambda$, then for any production $uXv\to uwv$ of $G$, $\sigma$ does not occur in $uwv$.

The reason for including the second condition is to ensure the possibility that $\lambda$ 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 $uXv\to uwv$ of $G$, $u=v=\lambda$, (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):=\{v\in T^{*}\mid\sigma\stackrel{*}{\to}v\},$ |

where $T=\Sigma-N$ is the set of terminals, and $\sigma\stackrel{*}{\to}v$ means that the word $v$ over $\Sigma$ is produced after a finite number of applications of the productions in $P$ to $\sigma$.

With condition 2, we see that a context-sensitive language contains $\lambda$ iff it is generated by a context-sensitive grammar containing $\sigma\to\lambda$. With condition 2, every context-free language is context-sensitive. Without condition 2, every $\lambda$-free context-free language is $\lambda$-free context-sensitive.

$\{a^{n}b^{n}c^{n}\mid n\geq 0\}$ and $\{a^{{2^{n}}}\mid n\geq 0\}$ are examples of context-sensitive languages that are not context-free, the second of which is $\lambda$-free.

Remarks.

1. A formal grammar $G$ is said to be

*length-increasing*if for every production $U\to V$ of $G$, the length of $U$ is at most the length of $V$: $|U|\leq|V|$. Every context-sensitive grammar not containing $\sigma\to\lambda$ (condition 2) is length-increasing. Conversely, any language generated by a length-increasing grammar is context-sensitive.2. The minimal automaton required for processing a context-sensitive languages is a bounded non-deterministic Turing machine (bounded linear automaton).

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

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. Given a context-sensitive language $L$ and a word $w$, it is decidable whether $w\in L$.

# References

- 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
- 2 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, (1969).

## Mathematics Subject Classification

68Q42*no label found*68Q45

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Context sensitive language (operating system)

What if...

The words (symbols) that you write on a surface are immediately interpreted by that surface (material)?

A few years ago, this concept would have been thought science fiction. Nano technology has enabled us to consider self-repairing paint, self-healing metals and medical technologies whereby nano-agents attack unwanted cells in our body.

If a nano-tube can be programmed to look for inconsistencies in a polymer, can we not engage them to react to those inconsistencies in the same way a computer reacts to simple instructions?

What if what we wrote on a surface enabled that surface to execute commands directly through "aware" nano-agents?

Appreciate your feedback.

Neil