Languages defined by context-free normal systems. (English) Zbl 0535.68035

Foundations of software technology and theoretical computer science, 3rd Conf., Bangalore/India 1983, 539-549 (1983).
[For the entire collection see Zbl 0527.00035.]
The paper studies normal systems (the derivation steps are of the form u\(v\Rightarrow wu\), (v,w) a production). The generative power of such systems under certain limiting assumptions is discussed. Th role of terminal subalphabets in normal systems with productions of the (A,w), A a (nonterminal) symbol, is investigated. If we introduce further conditions and transformations (e.g. codings, homomorphisms, nonerasing/erasing productions) we obtain more than 30 classes of languages. Inclusion theorems for the classes are derived. Relations to other rewriting systems are also discussed (e.g. L-systems).
Reviewer: J.Král


68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems


Zbl 0527.00035