摘要
研究了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.
出处
《华东理工大学学报(自然科学版)》
EI
CAS
CSCD
北大核心
2006年第4期492-496,共5页
Journal of East China University of Science and Technology
基金
国家自然科学基金资助项目(10101016)
关键词
元胞自动机
演化语言
正规语言
复杂性
cellular automata
evolution language
regular language
complexity