On the structure of context-sensitive grammars

Abstract

Consideration of the problem of explaining the use of context in generating noncontext-free languages. A number of existing results regarding the constraints placed on the form of the rules (i.e., on the context) of context-sensitive grammars are reviewed and interpreted. Three types of constraints are considered - namely, constraints which do not restrict the weak generative capacity of the class of grammars (i.e., all the context-sensitive languages are generated by grammars with these constraints), constraints which restrict the weak generative capacity to the extent that all context-sensitive languages are not generated but some noncontext-free languages are generated, and constraints which restrict the weak generative capacity to such an extent that only context-free languages are generated.