论文部分内容阅读
元胞自动机的复杂性问题始终是一个复杂而充满挑战的课题。
本文利用形式语言、自动机理论和符号动力学等方法来研究初等元胞自动机的语法复杂性，包括极限语言和演化语言复杂性。
本文推广了演化语言的概念，将演化语言推广到斜演化语言，并对7号初等元胞自动机的极限语言和宽度分别为1，2的斜演化语言从形式语言的角度进行复杂性分析，得出了如下结果：
(1)7号初等元胞自动机的极限语言是无限补正规语言；
(2)7号初等元胞自动机的宽度为1的右斜演化语言为有限补正规语言；
(3)7号初等元胞自动机的宽度为2的右斜演化语言的禁止字集合是非正规的上下文无关语言；
(4)7号初等元胞自动机的宽度为2的右斜演化语言不是正规语言。