On acceptors of iteration languages

Abstract

The classes of languages accepted by (unrestricted) PAC machines and (unrestricted) PDA²machines are characterized. Several extentions of the PAC machine model are defined and in particular: (i) a method is presented that for each class of K-iteration grammars provides a class ofacceptors for the corresponding class of languages, and (ii) it is shown that a simple (and natural) extension of a PDA²model yields a class of acceptors forthe class of recursively enumerable languages.

Keywords:

• Lsystems
• iteration grammars
• acceptros

C.R. Categories:

• 5.23
• 5.26
• 5.22