Context Free Normal Systems and ETOL Systems

摘要

The relationship between extended context free normal systems (a nondeterministic version of Tag systems of Post with deletion number equal to 1 and using nonterminals) and ETOL systems is considered. It is demonstrated that the class of languages generated by context free normal systems (denoted L(ECFN)) lies strictly between the clas of EOL languages (denoted L(EOL)) and the class of ETOL languages. Several characterizations of L(ECFN)) in terms of L(EOL)) are provided and a number of closure properties of L'(ECFN) are established.