grammars, a great variety of “somewhat restricted” grammars can be defined.
Not all cases yield interesting results; among the ones that do, the contextsensitive grammars have received considerable attention. These grammars
generate languages associated with a restricted class of Turing machines, linear
bounded automata, which we introduced in Section 10.5.
Definition 11.4
A grammar G = (V, T, S, P) is said to be context-sensitive if all productions
are of the form
x →y,
where x, y ∈ (V ∪ T) + and
This definition shows clearly one aspect of this type of grammar; it is
noncontracting, in the sense that the length of successive sentential forms can
never decrease. It is less obvious why such grammars should be called contextsensitive, but it can be shown (see, for example, Salomaa 1973) that all such
grammars can be rewritten in a normal form in which all productions are of the
form
xAy → xυy.
This is equivalent to saying that the production
A → υ
can be applied only in the situation where A occurs in a context of the string x on
the left and the string y on the right. While we use the terminology arising from
this particular interpretation, the form itself is of little interest to us here, and we
will rely entirely on Definition 11.4.
Context-Sensitive Languages and Linear Bounded
Not all cases yield interesting results; among the ones that do, the contextsensitive grammars have received considerable attention. These grammars
generate languages associated with a restricted class of Turing machines, linear
bounded automata, which we introduced in Section 10.5.
Definition 11.4
A grammar G = (V, T, S, P) is said to be context-sensitive if all productions
are of the form
x →y,
where x, y ∈ (V ∪ T) + and
This definition shows clearly one aspect of this type of grammar; it is
noncontracting, in the sense that the length of successive sentential forms can
never decrease. It is less obvious why such grammars should be called contextsensitive, but it can be shown (see, for example, Salomaa 1973) that all such
grammars can be rewritten in a normal form in which all productions are of the
form
xAy → xυy.
This is equivalent to saying that the production
A → υ
can be applied only in the situation where A occurs in a context of the string x on
the left and the string y on the right. While we use the terminology arising from
this particular interpretation, the form itself is of little interest to us here, and we
will rely entirely on Definition 11.4.
Context-Sensitive Languages and Linear Bounded