Nonterminals Versus Homomorphisms in Defining Languages for Some Classes of Rewriting Systems.

摘要

Given a rewriting system G (its alphabet,the set of productions and the axiom) one can define the language of G by (1) taking out of all strings generated by G only those which are over a distinguished subalphabet of G,or (2) translating the set of all strings generated by G by a fixed homomorphism. The trade-offs between these two mechanisms for defining languages are discussed for both, 'parallel'rewriting systems from developmental systems hierarchy and 'sequential'rewriting systems from the Chomsky hierarchy.