Report Number: CS-TR-75-493
Institution: Stanford University, Department of Computer Science
Title: Describing automata in terms of languages associated with their peripheral devices.
Author: Kurki-Suonio, Reino
Date: May 1975
Abstract: A unified approach is presented to deal with automata having different kinds of peripheral devices. This approach is applied to pushdown automata and Turing machines, leading to elementary proofs of several well-known theorems concerning transductions, relationship between pushdown automata and context-free languages, as well as homomorphic characterization and undecidability questions. In general, this approach leads to homomorphic characterization of language families generated by a single language by finite transduction.