Karakterisation af oversættelse for de til Chomsky-hierarkiet hørende automater

Abstract

This publication is the author's master's thesis. It treats the following problem: If one takes a ''Chomsky-automaton'' (i. e. a finite state automaton, a push-down automaton, a linear bounded automaton or a Turing Machine) and equips it with output one obtains the corresponding translator. Define the graph of a translator as the set of pairs (x, y) where input x belongs to the language accepted by the automaton and y is the ouput produced while processing x . How can such graphs be characterized ?

A characterization is given for all Chomsky types in terms of pair grammars generating the graphs as well as in terms of homomorphic images of a language of corresponding type. The publication was intended to be used as material in connection with a course on automata theory and hence it contains proofs of theorems appearing elsewhere in the literature.