FINITE AUTOMATA OVER FREE GROUPS

Abstract

Finite automata are extended by adding an element of a given group to each of their configurations. An input string is accepted if and only if the neutral element of the group is associated to a final configuration reached by the automaton. We get a new characterization of the context-free languages as soon as the considered group is the binary free group. The result cannot be carried out in the deterministic case. Some remarks about finite automata over other groups are also presented.