Automata
As the terminology suggests, context-sensitive grammars are associated with a
language family with the same name.
Definition 11.5
A language L is said to be context-sensitive if there exists a context-sensitive
grammar G, such that L = L (G) or L = L (G) ∪{λ}.
In this definition, we reintroduce the empty string. Definition 11.4 implies
that x → λ is not allowed, so that a context-sensitive grammar can never generate
a language containing the empty string. Yet, every context-free language without
λ can be generated by a special case of a context-sensitive grammar, say by one
in Chomsky or Greibach normal form, both of which satisfy the conditions of
Definition 11.4. By including the empty string in the definition of a contextsensitive language (but not in the grammar), we can claim that the family of
context-free languages is a subset of the family of context-sensitive languages.
Example 11.2
The language L = {a n b n c n : n ≥ 1} is a context-sensitive language. We show this
by exhibiting a context-sensitive grammar for the language. One such grammar
is
We can see how this works by looking at a derivation of a 3 b 3 c 3 .