Formal Languages and Finite Cellular Automata
Mats G. Nordahl
Institute of Theoretical Physics, S-412 96 Göteborg, Sweden
Abstract
A one-dimensional cellular automaton rule with specified boundary conditions can be considered as acting simultaneously on all finite lattices, which gives a mapping between formal languages. Regular languages are always mapped to regular languages, context-free to context-free, context-sensitive to context-sensitive, and recursive sets to recursive sets. In particular, the finite time sets on finite lattices are regular languages. The limit set on finite lattices (the periodic set) is shown to be neither a regular nor an unambiguous context-free language for certain additive rules with chaotic behavior, and for rules that can simulate one of these additive rules through a finite blocking transformation. The relation between cellular automata on finite and infinite lattices is discussed.
