If each production of G is of the form x A y [right arrow] xuy, where x, y [member of] [V.sup.*], A [member of] V - T, u [member of] [V.sup.+], then G is a context-sensitive grammar. The family of context-sensitive languages is denoted by L(CS).
Lemma 1 () For every context-sensitive grammar there exists an equivalent grammar in the Kuroda normal form.
Virkkunen proved that propagating scattered context grammars which use leftmost derivations are as powerful as context-sensitive grammars. This paper brings a significantly simplified proof of this result.
: the languages defined by these grammars are accepted by linear bounded automata.
After a quick overview of necessary prerequisites such as set and graph theory and the study of relations and general logic, the author follows a path that narrows its themes from chapter to chapter: from regular to context-free languages and their models, to Turing machines and specific computation issues, including computability and decidability and general and context-sensitive grammars
. Concluding discussions of modern trends in specific grammar types and two appendices (indices of special symbols and language models) provide and open-ended note and indicate avenues for future research and more advanced study.
The context-free network grammars can be replaced by context-sensitive grammars
. Context-sensitive grammars
can generate networks such as square grids and complete binary trees that cannot be generated by the context-free grammars.