元胞自动机是自然界许多复杂系统的理想化数学模型,它可以模拟许多自然现象与生命现象,大量未解决的问题为这个困难而有趣的领域展现了广阔的前景。 自von Neumann首次提出元胞自动机的思想至今已有半个世纪,学者们对元胞自动机进行了大量的研究,然而现在对元胞自动机仍然缺少有效的数学方法,严格的数学结果也很少。本文探求一种新的研究元胞自动机的方法,使用禁止字理论、计算机搜索和符号动力学的方法对于256个初等元胞自动机生成的时间序列(只观察一个位点上的演化所得到的序列)进行复杂性分析。借助时间序列所具有的特性通过研究它的禁止字来研究演化语言(本文所指的演化语言如无特别标注都是指宽度为1的时间序列所组成的语言),确定了大多数初等元胞自动机生成的时间序列所处的Chomsky层次以及严格的数学表达式。 在对初等元胞自动机时间序列的禁止字分析之后,按照它们演化语言的复杂程度分为以下四类:第Ⅰ类为满射,第Ⅱ类为有限补正规语言,第Ⅲ类为无限补正规语言,第Ⅳ类很有可能是非正规语言。 第Ⅰ类情况中的初等元胞自动机没有禁止字,其宽度1的演化语言为最大可能的正规语言,并且这一类中部分元胞自动机的任意宽度演化语言都是正规的。 第Ⅱ类情况中的初等元胞自动机只有有限多个禁止字,因此其宽度1的演化语言为有限补正规语言。 第Ⅲ类情况中的初等元胞自动机有无限多个禁止字,但禁止字集是正规语言,经过理论分析知道其演化语言为无限补正规语言。此类情况中一个代表性的例子是27号初等元胞自动机。 第Ⅳ类情况中的初等元胞自动机也有无限多个禁止字,但是它们的演化语言很有可能不是正规语言,这类情况比前三种情况复杂的多,对这一类初等元胞自动机的讨论尚未全部完成。本文给出了其中56号初等元胞自动机的宽度为1的演化语言是上下文无关语言的详细证明,并给出了严格的数学表达式。