文献类型：期刊文献

中文题名：122号元胞自动机的演化语言复杂性

英文题名：Evolution Language Complexity of Cellular Automaton of Rule 122

作者：江志松[1]

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

年份：2006

卷号：32

期号：4

起止页码：492

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：CSTPCD;;EI(收录号：2006229913090);Scopus;北大核心:【北大核心2004】；CSCD:【CSCD2011_2012】；

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

语种：中文

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

外文关键词：cellular automata ; evolution language ; regular language ; complexity

摘要：研究了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.