122号元胞自动机的演化语言复杂性
Evolution Language Complexity of Cellular Automaton of Rule 122
-
摘要: 研究了122号初等元胞自动机的演化语言,证明了其宽度为1的演化语言是正规的,宽度大于1的演化语言不是正规的。结果表明:仅用有限自动机是无法接受由122号初等元胞自动机产生的演化语言。Abstract: The evolution languages of an elementary cellular automaton of rule 122 were studied.Its evolution language with width 1 is proved to be regular but the evolution languages with the width greater than 1 become irregular.Therefore the finite automaton cannot accept the evolution languages generated by elementary cellular automaton of rule 122.