Article
Full entry |
PDF
(0.8 MB)
Feedback
PDF
(0.8 MB)
Feedback
Keywords:
pushdown transducer; self-reproducing pushdown transduction; recursively enumerable languages
pushdown transducer; self-reproducing pushdown transduction; recursively enumerable languages
Summary:
After a translation of an input string, $x$, to an output string, $y$, a self- reproducing pushdown transducer can make a self-reproducing step during which it moves $y$ to its input tape and translates it again. In this self- reproducing way, it can repeat the translation $n$-times for any $n \ge 1$. This paper demonstrates that every recursively enumerable language can be characterized by the domain of the translation obtained from a self- reproducing pushdown transducer that repeats its translation no more than three times.
References:
[1] Harrison M. A.: Introduction to Formal Language Theory. Addison–Wesley, Reading 1978 MR 0526397 | Zbl 0411.68058
[2] Kleijn H. C. M., Rozenberg G.: On the generative power of regular pattern grammars. Acta Inform. 20 (1983), 391–411 MR 0732313 | Zbl 0541.68048
[3] Meduna A.: Automata and Languages: Theory and Applications. Springer, London 2000 MR 1778364 | Zbl 0951.68056
[4] Meduna A.: Simultaneously one-turn two-pushdown automata. Internat. Computer Math. 80 (2003), 679–687 DOI 10.1080/0020716031000070616 | MR 1984796 | Zbl 1103.68587
[5] Meduna A., Kolar D.: Regulated pushdown automata. Acta Cybernet. 14 (2000), 653–664 MR 1790232 | Zbl 1011.68049
[6] Revesz G. E.: Introduction to Formal Languages. McGraw–Hill, New York 1983
Search
Partner of
