Multi grammars

Abstract

The theory of selective substitution grammars is an attempt to provide a common framework for a number of seemingly different rewriting systems. The core of a selective substitution grammar is its selector (language), which prescribes which occurrences of letters in a current sentential form must be rewritten. Three rudimentary forms of selectors, studied until now are sequential, parallel, and continuous selectors. This paper is concerned with building more involved selectors, starting with rudimentary ones and using operations of union and concatenation. The language generating power of several classes of rewriting systems obtained in this way is investigated.

Keywords:

• selective substitution grammars
• sequential and parallel rewriting
• grammatical normal forms
• hierarchies of language families

C.R. Categories::

• (new classification) E.4.2
• E.4.3.