Describing automata in terms of languages associated with their peripheral devices.

[摘要] 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.

[学科分类] 计算机科学（综合）