An Introduction to Formal Languages and Automata, 7th Edition

11.3 CONTEXT-SENSITIVE GRAMMARS AND LANGUAGES

Between the restricted, context-free grammars and the general, unrestricted grammars, a great variety of “somewhat restricted” grammars can be defined. Not all cases yield interesting results; among the ones that do, the context-sensitive 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\to y,$$

where x, y ∈ (V ∪ T)⁺ and

$\left|x\right|\le \left|y\right|.$

(11.15)

This definition shows clearly one aspect of this type of grammar; it is noncontracting, in the sense ...