| There are many complex systems in nature, the sturctures of their conponents 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. 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 this paper we study the complexity of evolution languages generated from elementary cellular automaton of rule 126 and rule 122 by the tools of formal language theory and symbolic dynamics. It is proved that:(1) For elementary cellular automaton of rule 126, its 1-evolution language is regular but its n-evolution language (n≥2) is not regular.(2) For elementary cellular automaton of rule 122, its 1-evolution language is regular but its n-evolution language (n≥2) is not context-free. |
PDF Full Text Request