Cellular automata as regular languages

Cellular automata, Finite state machines

From (Hanson and Crutchfield 1997):

Finite state machines are appropriate for investigating pattern dynamics of CAs for a number of reasons, among which we may note the following:

  • FAs encompass the full range of behavior types from periodic to complex to random;
  • Characterization of patterns using FAs makes possible a definition of pattern complexity which is both natural and computable in practice;
  • Ensemble evolution in the space of regular languages is closed under the CA rule;
  • The CA update rule is itself an FST;
  • Automated inference techniques exist for reconstructing FAs from experimental data


Hanson, James E., and James P. Crutchfield. 1997. “Computational Mechanics of Cellular Automata: An Example.” Physica D: Nonlinear Phenomena, Lattice Dynamics, 103 (1):169–89.

Links to this note

← Back to Notes