Comments on universal and left universal grammars, context-sensitive languages, and context-free grammar forms

A grammar G is left universal (universal) for a family of languages ℒ and finite alphabet Σ with respect to a family of languages ℒ1, if ℒ restricted to subsets of Σ* is the family of subsets of Σ* obtained by using members of ℒ1 to control left-to-right derivations (unrestricted derivations) of G; if ℒ1 is the family of regular sets, G is called simply left universal or universal for ℒ and Σ. There is no context-sensitive grammar universal for the class of context-sensitive languages even over a one-letter alphabet. There is a context-free grammar which is left universal for the class of recursively enumerable languages with respect to the family of linear context-free languages. There is a linear context-free grammar which is universal and left universal for the family of linear contextfree languages. If G is a nontrivial left-derivation-bounded context-free grammar, then for each finite alphabet Σ there is a left-derivation-bounded contextfree grammar which is left universal for ℒ and Σ, where ℒ is the family of languages generated by interpretations of G as a context-free grammar form