论文部分内容阅读
元胞自动机可以看成为一类无穷维离散的动力系统，它们具有空间、时间和状态都离散的特点。元胞自动机是一种理想化数学模型，可以被用来模拟许多物理、生物和化学等复杂现象。
本文以形式语言和符号动力学理论为基础，运用禁止字、逆斜周期不变串和确定性有限自动机等工具，研究了51个非法初等元胞自动机的极限语言复杂性。根据禁止字的增长规律将非法初等元胞自动机分为三类：第一类有限步后无新禁止字产生的非法初等元胞自动机，共有24个；第二类新禁止产生一般呈线性增长的非法初等元胞自动机，共有15个；第三类新禁止字产生没有规律增长的非法初等元胞自动机，共有12个。本文证明了这51个非法初等元胞自动机的极限语言都是正规语言，最后还对所有88个初等元胞自动机的极限语言复杂性作了小结。