Search

A linear context-free language which is not acceptable by a finite probabilistic automaton is given, and it is shown that the family of stochastic languages is not closed under concatenation and homomorphism.

The congruence relations of an automaton are of interest for various reasons. For example they are relevant for minimization procedures and they are suitable for decomposing the automaton in a specific way which is of technical importance [Hartmanis et al.]. In this paper we have investigated the interconnection between the automorphism groupG (A) and the latticeR (A) of congruence relations of an automaton. This interconnection is primarily based on a Galois connection between the subgroup lattice ofG (A) and the latticeG (A), which characterizes a subset ofR (A) in terms of groups. Assuming that group theory is the trivial part of the theory of semigroups, the attention is directed to the remainder ofR (A) which is not characterized byG (A) in the way mentioned above. This remainder, however, has not been inspected for the general case, which seems to be a hopeless task, but for the class of so called right regular automata. In the last section some theoretical background for a systematic procedure in obtaining all congruence relations of an automaton as well as its endomorphism semigroup has been developed.

Publisher Summary This chapter focuses on the recognizers (Rabin-Scott automata). A deterministic automaton is a special case of a nondeterministic one; hence, a set of tapes recognized by a deterministic automaton is recognized by a nondeterministic one. The chapter also shows that the opposite is also true. Various theorems are proved in the chapter. Various examples of regular and non-regular sets are presented. A reduced automaton is one which has no proper homomorphic images, provided that its input set is held constant. Every semiautomaton with more than one state has a proper homomorphic image: the one-state semi-automaton. The regular sets corresponding to an automaton and to its homomorphic image are equal.

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.