CYCLE ANALYSIS FOR DETERMINISTIC FINITE STATE AUTOMATA

摘要

A method for the determination of all cycles of deterministic finite state automata is presented. Using a finite field description GF(2) these automata are shown to correspond to multilinear state equations. Basic results from feedback shift register theory are recalled and developed towards a complete analysis tool for affine-linear automata. The multilinear case is reduced to the affine-linear case by application of a linearizing constant state feedback and a linear state space embedding. Some brief examples illustrate the basic ideas.