In this bachelor thesis we present some interesting examples and results on groups generated by Mealy automata.
In the first section we introduce the input and output of an automaton as sequences of symbols from an alphabet X, and we discuss their properties. In particular, we present the set X^* of finite sequences as the set of vertices of a rooted tree. Then we go on to the formal definition of a finite deterministic Mealy automaton (we will simply call it an automaton) A, and we provide some examples of automata given by Moore diagrams (graph representations of automata). We define the concept of an initial automaton and its action.
In the second section we give an abstract characterization of actions of automata: the notion of a synchronous automatic transformation f. We pay a special attention to invertible automata. Then we provide the definition of a group generated by an automaton.
In the third section we describe some algebraic structures that arise in connection to groups of automata. We first revise the notions of left and right actions of a group on a set and on a group, the semidirect product construction and finally the wreath product construction. We then study the relationship of these notions with automata.
In the fourth section we present the classification of groups generated by 2-state automata over a 2-letter-alphabet. Before formulating the result we introduce two important groups that arise in this theorem, i.e., the infinite dihedral group and the lamplighter group. The latter group can be realized as a wreath product of the infinite cyclic group Z and the two-element group Z/2Z. Then we define a synchronous automatic transformation called the adding machine. Finally we present a detailed account of a part of the proof of the classification theorem. It is based on careful case consideration.
|
