论文部分内容阅读
自然界存在着许许多多的复杂系统，这些系统的每一部分结构可以非常简单，但由于各部分之间存在着一定的关联(耦合)，最后表现出的整体性态可以极其复杂。元胞自动机就是研究复杂系统的理想化的一种数学模型，它最早是由Von Neumann在研究生命系统的自我复制现象时提出的，后来被广泛地用于模拟多种自然现象和生命现象。本文以形式语言理论和符号动力学为工具研究126号和122号初等元胞自动机的演化语言的复杂性。证明了：(1)126号初等元胞自动机的1-演化语言是正规的；而n-演化语言(n≥2)不是正规的。(2)122号初等元胞自动机1-演化语言是正规的；而n-演化语言(n≥2)是上下文有关语言，但不是上下文无关语言。