SYMMETRY GROUPS OF AUTOMATA

Symmetry transformations on the input and output code spaces of determ inistic finite automata (DFA) are introduced. We show that the symmetr y groups of transformations are produced by group DFA (gDFA) whose set of states and set of inputs are subgroups of the symmetric groups S-q and S-k, respectively (q is the number of states and k the number of input symbols). The set of transitions of a gDFA is also a group. The symmetries of the n-moment delay DFA, relevant for cellular automata, are studied in detail. In particular, we show that the n-moment delay DFA on two symbols are self-symmetric. The symmetry gDFA of the 2-mome nt delay DFA on two symbols is displayed in detail. An algorithm to co nstruct the symmetry gDFA of arbitrary DFA is given. An application of gDFA to cellular automata dynamics is mentioned.