Control sets on context-free grammar forms

摘要

For a context-free grammar form G, the result of the G-control operator acting on a family of languages ℒ is defined as the family of languages formed by using members of ℒ to control left-to-right derivations of all grammars which are interpretations of G. If G is left derivation bounded, the G-control operator takes a full semiAFL ℒ into a full semiAFL which can be characterized by homomorphic replications on members of ℒ and takes context-free full semiAFLs into quasi-realtime full semiAFLs, quasi-realtime full semiAFLs into quasi-realtime full semiAFLs and context-sensitive full semiAFLs into context-sensitive full semiAFLs. If G is nonterminal bounded and self-embedding and ℒ is a full semiAFL not closed under the G-control operator then repeated applications of the G-control operator produce a strictly increasing chain of full semiAFLs. If G is not left derivation bounded the G-control operator can take the family of linear context-free languages onto the family of r.e. languages even if G is not self-embedding and all interpretations of G generate regular sets.