Complexity Of The Elementary Cellular Automaton

There are many complex systems in nature, the sturctures of their components may be quite simple, however, they can display very rich and complex global behaviors since there are local interactions among the components.Cellular automata are ideal mathematical models in studying complex systems. Cellular automata can be seen as discrete dynamical systems. The time, space and state are discrete, and every cell has finite states. Historically, the first cellular automaton was proposed by von Neumann to simulate the self-reproductive phenomena in living systems. Since then they have been used widely to simulate various natural and life phenomena. In 1984, Wolfram use formal language to study cellular automaton, then the study of cellular automaton' complexity had begined. In this paper we study the complexity of evolution languages generated from elementary cellular automaton of rule 126 and the complexity of limiting languages of elementary cellular automaton of rule 23 and rule 77 by the tools of formal language theory and symbolic dynamics. It is proved that:(1) For elementary cellular automaton of rule 126, its n-evolution language (n≥2) is not context-free but context-sensitive.(2) For elementary cellular automaton of rule 23, its limiting language is regular.(3) For elementary cellular automaton of rule 77, its limiting language is regular.