Size, index, and context-sensitivity of controlled partition grammars

Abstract

Controlled partition grammars (CPGs) were designed to apply to certain needs of linguists. General CPGs generate exactly all context-sensitive languages. CPGs have two parameters:size and index. The partition index of CPGs can be bounded by two, while CPGs with partition index one generate exactly the class of context-free languages. The size (of the partition blocks) of CPGs can be bounded by two, while CPGs of size one generate a class of languages properly contained in the class of contextsensitive languages. If one can eliminate recursive productions of the form A→B in a CPG then deterministic and nondeterministic lba's are equivalent. © 1977 Springer-Verlag New York Inc.