122号元胞自动机的演化语言复杂性  

Evolution Language Complexity of Cellular Automaton of Rule 122

作　　者：江志松[1] 

机构地区：[1]华东理工大学数学系,上海200237

出　　处：《华东理工大学学报（自然科学版）》2006年第4期492-496,共5页Journal of East China University of Science and Technology

基　　金：国家自然科学基金资助项目(10101016)

摘　　要：研究了122号初等元胞自动机的演化语言,证明了其宽度为1的演化语言是正规的,宽度大于1的演化语言不是正规的。结果表明:仅用有限自动机是无法接受由122号初等元胞自动机产生的演化语言。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.

关 键 词：元胞自动机 演化语言 正规语言 复杂性 

分 类 号：O231.5[理学—运筹学与控制论]