Open AccessNonterminals, Homomorphisms, and Codings in Different Variations of 0L-Systems
Author(s) -
Mogens Nielsen,
Grzegorz Rozenberg,
Arto Salomaa,
Sven Skyum
Publication year - 1974
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v3i21.6440
Subject(s) - homomorphism , nondeterministic algorithm , mathematics , generative grammar , natural language processing , discrete mathematics , artificial intelligence , computer science , linguistics , philosophy
The use of nonterminals versus the use of homomorphisms of different kinds in the basic types of deterministic OL-systems is studied. A rather surprising result is that in some cases the use of nonterminals produces a comparatively low generative capacity, whereas in some other cases the use of nonterminals gives a very high generative capacity. General results are obtained concerning the use of erasing productions versus the use of erasing homomorphisms. The paper contains a systematic classification of the effect of nonterminals, codings, weak codings, nonerasing homomorphisms and nomomorphisms for all basic types of deterministic OL-languages, including table languages. Continuing the work begun in Part I of this paper, we consider now variations of nondeterministic OL-systems. The present Part ll of the paper contains a systematic classification of the effect of nonterminals, codings. weak codings, nonerasing homomorphisms and homomorphisms for all basic variations of nondeterministic OL-languages, including table languages.