（应用数学专业论文）初等元胞自动机的复杂性研究.pdf

初等元胞自动机的复杂性研究中文摘要 初等元胞自动机的复杂性研究 摘要 自然界中存在着许许多多的复杂系统，这些系统的每一部分的结构可以非常简 单，但由于各部分之间存在着一定的关联( 耦合) ，最后表现出的整体性态可以极其复 杂 元胞自动机就是研究复杂系统的一种理想化的数学模型元胞自动机可以看成一个 离散的动力系统，特点是空间、时间和状态都离散，且每一个元胞只取有限个状态 它最早是由r o l ln e u m a n n 在研究生命系统的自我复制现象时提出的，后来被广泛地用 于模拟多种自然现象和生命现象。1 9 8 4 年，w o l f r a m 引进形式语言来对元胞自动机进 行研究，从而开始了对元胞自动机语言复杂性方面的研究本文以形式语言理论和符 号动力学为工具，研究了1 2 6 号初等元胞自动机的演化语言复杂性，以及2 3 号和7 7 号初等元胞自动机的极限语言复杂性，证明了t ( 1 ) 1 2 6 号初等元胞自动机的站一演化语言( n 2 ) 不是上下文无关的，而是上下 文有关的 ( 2 ) 2 3 号初等元胞自动机的极限语言是正规的 ( 3 ) 7 7 号初等元胞自动机的极限语言是正规的 关键词：元胞自动机；复杂性；形式语言；演化语言；极限语言 作者：戴燕红 指导教师：王益 c o m p l e x i t yo ft h ee l e m e n t a r yc e l l u l a ra u t o m a t o n a b s t r a c t c o m p l e x i t yo ft h ee l e m e n t a r yc e l l u l a ra u t o m a t o n ab s t r a c t t h e r ea r em a n yc o m p l e xs y s t e m si nn a t u r e ，t h es t u r c t u r e so ft h e i rc o m p o n e n t sm a yb e q u i t es i m p l e ，h o w e v e r ，t h e yc a nd i s p l a yv e r yr i c ha n dc o m p l e xg l o b a lb e h a v i o r ss i n c et h e r e a r el o c a li n t e r a c t i o n sa m o n gt h ec o m p o n e n t s c e l l u l a ra u t o m a t aa r ei d e a lm a t h e m a t i c a lm o d e l si ns t u d y i n gc o m p l e xs y s t e m s c e l l u l a r a u t o m a t ac a nb es e e n 躺d i s c r e t ed y n a m i c a ls y s t e m s t h et i m e ，s p a c ea n ds t a t ea r ed i s c r e t e ， a n de v e r yc e l lh a sf i n i t es t a t e s h i s t o r i c a l l y , t h ef i r s tc e l l u l a ra u t o m a t o nw a sp r o p o s e db yy o n n e u m a n nt os i m u l a t et h es e l f - r e p r o d u c t i v ep h e n o m e n ai nl i v i n gs y s t e m s s i n c et h e nt h e y h a v eb e e nu s e dw i d e l yt os i m u l a t ev a r i o u sn a t u r a la n dl i f ep h e n o m e n a i n1 9 8 4 ，w o l f r a m u s ef o r m a ll a n g u a g et os t u d yc e l l u l a ra u t o m a t o n ，t h e nt h es t u d yo fc e l l u l a ra u t o m a t o n c o m - p l e x i t yh a db e g i n e d i nt h i sp a p e rw es t u d yt h ec o m p l e x i t yo fe v o l u t i o nl a n g u a g e sg e n e r a t e d f r o me l e m e n t a r yc e l l u l a ra u t o m a t o no fr u l e1 2 6a n dt h ec o m p l e x i t yo fl i m i t i n gl a n g u a g e so f e l e m e n t a r yc e l l u l a ra u t o m a t o no fr u l e2 3a n dr u l e7 7b yt h et o o l so ff o r m a ll a n g u a g et h e o r y a n ds y m b o l i cd y n a m i c s i ti sp r o v e dt h a t ： ( 1 ) f o re l e m e n t a r yc e l l u l a ra u t o m a t o no fr u l e1 2 6 ，i t sn - e v o l u t i o nl a n g u a g em 22 ) i sn o t c o n t e x t - f r e eb u tc o n t e x t - s e u s i t i v e ( 2 ) f o re l e m e n t a r yc e l l u l a ra u t o m a t o no fr u l e2 3 ，i t sl i m i t i n gl a n g u a g ei sr e g u l a r ( 3 ) f o re l e m e n t a r yc e l l u l a ra u t o m a t o no f r u l e7 7 ，i t sl i m i t i n gl a n g u a g ei sr e g u l a r k e y w o r d s ：c e l l u l a ra u t o m a t a ；c o m p l e x i t y ；f o r m a ll a n g u a g e ；e v o l u t i o nl a n g u a g e ；l i m i t i n g l a n g u a g e i i w r i t t e nb yd a ly a n h o n g s u p e r v i s e db yp r o f w a n gy i 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作所 取得的成果除文中已经注明引用的内容外，本论文不含其他个人或集体已经发表或 撰写过的研究成果，也不含为获得苏州大学或其它教育机构的学位证书而使用过的材 料对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明本人承 担本声明的法律责任 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合作部、中国 社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电子文档，可以采 用影印、缩印或其他复制手段保存论文本人电子文档的内容和纸质论文的内容相一 致除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论 文的全部或部分内容论文的公布( 包括刊登) 授权苏州大学学位办办理 导师签名： 初等元胞自动机的复杂性研究第一章元胞自动机简介 1 1 引言 第一章元胞自动机简介 自然界存在着许许多多的复杂系统，这些系统的每一部分的结构和性质可以非常 简单，但由于各部分之间存在着一定的关联( 或称耦合) ，最后表现出的整体性态却可 以极其复杂【l ，2 1 元胞自动机的出现为处理这样的( 非线性) 复杂系统提供了新的方 法，它是研究复杂系统的一种理想化的数学模型元胞自动机可以看成为类无穷维 动力系统，其特点是空间、时间和状态都离散，同时每个变量只取有限个状态 二十世纪四十年代末，y o nn e u m a n n 受图灵机、早期神经网络和控制自动机理论的 影响，在研究生命的自我复制问题时提出一种数学模型1 3 ，4 ，5 1 ，孕育了被他称为。元 胞( c e l l ) ”的思想此后，许多学者对元胞自动机作了进一步的研究，一方面是构造具 有自复制功能的元胞自动机，另一方面是通过用数学方法研究元胞自动机的性质来研 究自复制行为的本质二十世纪六十年代h e d l u n d 建立了元胞自动机的数学理论，他 在论文【6 1 6 中对元胞自动机作了较为全面的研究，证明了许多深刻的结论七十年代 c o n w e y 提出了著名的生命游戏( g a m eo fl i f e ) ，它事实上只是一个二维的元胞自动 机，却能模拟出自然界中生存、灭绝、竞争和繁衍等生命活动的现象生命游戏是元 胞自动机广阔应用背景的一个方面的体现，引起了广泛的关注到了八十年代，随着 计算机的逐渐普及，w o l f r a m 引进形式语言，并采用动力系统，代数、统计，混沌、 非线性等方法对元胞自动机进行研究，从而开始了对元胞自动机语言复杂性方面的研 究，迎来了元胞自动机研究的又一个高潮讨论元胞自动机的复杂性的多数工作是研 究它们的极限集和演化序列的复杂性这方面成功的例子见【7 ，8 ，9 ，1 0 ，1 1 ，1 2 ，1 3 ，1 4 1 元胞自动机的理论研究促进了其应用的发展，在并行计算模型，自然模拟模型、密码 学等方面获得了较好的应用1 1 5 1 w o l f r a m 通过大量的计算机实验，按照在计算机上所观察到的动力学行为将所有元 胞自动机分成以下四类 1 6 1 ； ( 1 ) 趋于个空间平稳构形，即每个元胞处于相同状态； ( 2 ) 趋于一系列简单的稳定结构或周期结构； ( 3 ) 表现出混沌的非周期行为； ( 4 ) 出现复杂的局部结构，或者说是局部混沌，其中有些会不规则的传播 初等元胞自动机的复杂性研究第一章元胞自动机简介 前三类相当于低维动力系统中常见的不动点、周期轨和混沌，第四类则被认为是可 以与生命系统等复杂系统相比拟的自组织行为按照w o l f r a m 的观点，元胞自动机的 动力学行为可以归纳成数量如此之少的四类，这是非常有意义的发现它反映出这种 分类可能具有某种普适性很可能有许多物理系统或生命系统可以按照这样的分类进 行研究，尽管在细节上可以不同，但每一类中的行为在定性上是相同的这是第一次 对元胞自动机进行分类，而且比较直观但这种分类是现象学分类，并不是严格的数 学定义对于给定的一个元胞自动机，到底属于那一类，有时是有争议的后来许多 学者为了完善这个分类，从各种不同的角度给出了许多不同的分类 1 7 ，1 8 ，1 9 j w o l f r a m 还创造性地应用理论计算机科学中的工具来进行元胞自动机的研究他证 明了元胞自动机在任何有限时刻演化得到的形式语言都是正规语言，并关于极限语言 提出若干设想，多年来这一直是动力系统研究的热点之一1 2 0 另一方面，元胞自动机研究中还可以引入粗粒化思想【n l 】以一维为例，在双侧无 限的格点上固定选择n 个相邻位置( 即观察窗口) ，研究构形轨道在其中的演化这 相当于把元胞自动机的构形空间按照观察窗口中的n 个元胞的状态划分成有限个子空 间，然后以轨道上的每个构形所处的子空间来代表构形本身 1 9 9 0 年j e n 讨论了包括9 0 号在内的若干初等元胞自动机在单个位置上的演化序 列，证明除平凡情况外都是非周期的泓1 这个结果跟计算机实验结果一致，很好地体 现了9 0 号初等元胞自动机的某种复杂性，获得广泛的关注【砌关于元胞自动机的演 化语言的研究，g i l m a n 、k u r k a 、m a a s s 等人做了不少的工作【1 9 ，2 4 1 本文主要用形式语言和符号动力学来研究元胞自动机的复杂性第一章简要介绍了 元胞自动机基本理论；第二章介绍了形式语言与自动机理论；第三章讨论了1 2 6 号初 等元胞自动机的演化复杂性；第四章对2 3 号和7 7 号初等元胞自动机的极限语言进行 了分析；最后一章给出了结论下节先给出元胞自动机的定义 1 2元胞自动机的定义 首先介绍一维元胞自动机的定义，高维元胞自动机的定义可由一维元胞自动机的 定义推广得到 考虑在双侧无穷直线上有无限多个分布在整数格点上的元胞，每个元胞有七个状 态，用符号0 , i ，七一i 表示 2 初等元胞自动机的复杂性研究第一章元胞自动机简介 令s = o ，l ，七一1 ) 代表每个元胞的状态集合双侧无穷序列 z = z l z o 1 ，z i s 称为元胞自动机的一个构形，所有构形的集合称为构形空间，记为s z 我们假定时间是离散的，对一个构形来说，每个元胞都同时发生变化 记为元胞自动机在t 时刻的构形，则时刻t + 1 的构形z t + 1 完全由矿决定：时 刻+ 1 的第i 个元胞的状态是由时刻t 的第i 个元胞以及相邻距离不超过r 的2 t 个 元胞的状态所决定的，用公式写出来即 z t + 1 = ，( z i 州，z ：- l z ：，z t + 1 ，z i + ，) ， 其中，与t ，t 无关事实上，是铲件1 到s 的一个映射利用，可诱导出映射 f ：s z 一舻，满足 f 0 ) i = ，( 以一r ，苁一1 ，以，x i + i ，z 件r ) 为了规范化，我们把上面的叙述写成如下定义。 定义1 1 映射f ：s 2 _ s z 称为个元胞自动机，若存在r 0 及f ：驴+ l s 使得 对任意的构形z = x - 1 z o z l ，满足 f ( z 五= f ( ：v i r ，祝一1 ，z i ，x i + i ，x i - t - r ) ， ，称为元胞自动机的局部规则，r 称为邻域半径，f 称为元胞自动机的全局规则 如果把元胞自动机看成某一现象的演化，那么它存在局部规则可以解释成：一件事 情会不会发生只与周围有限范围内的条件有关，与时间，地点无关这表明了元胞自 动机的局部性、定常性与空间齐性的性质 定义1 2 若元胞自动机的邻域半径为，= 1 ，状态数为k = 2 ，令状态集为a = t 0 ，1 ， 则元胞自动机f ：a z _ a z 称为初等元胞自动机 本文主要讨论初等元胞自动机，即状态数为2 而邻域半径为1 的一维元胞自动机 初等元胞自动机的局部规则事实上是映射f ：a 3 一a ，满足 z ：+ l = ，( z ：一l ，z t ，x 。t + 1 ) ， v 蕾z 3 初等元胞自动机的复杂性研究第一章元胞自动机简介 全局规则f 满足f ( z k = ，( 嗣一1 ，鼢，z 件1 ) ，i z 在铲上定义移位算子盯为口( z ) = x i + 1 ，i z 定义连续映射f ：s z s z 若f 与口可交换，即对任意的z s z ，有f ( 口( z ) ) = 盯( f ( 茁) ) ，则称f 为元胞自动机 此定义与定义1 1 等价，即对于与仃可交换的连续映射f ，必存在r 0 和局部映 射，：铲件1 _ s ，使得对每个构形z = z l x o x l ，t z ，有 f ( z ) i = ，( z i 叶，z 一1 ，z t ，戤+ 1 ，z i + r ) 同样地，f 是元胞自动机的全局映射 1 3元胞自动机演化语言 粗粒化思想是研究动力系统的一种重要方法一个非常著名的例子是s m a l e 马蹄， 另一个很典型的例子是单峰映射的粗粒化。对个系统恰当的进行粗粒化是非常重要 的如果在粗粒化过程中所丢失的信息对我们研究的目标无关，那么这样的粗粒化就 比较合适它可以帮助我们除掉许多无用的干扰信息，更容易抓住问题的本质 元胞自动机可看成是复杂系统的离散化( 粗粒化) 模型【7 ，8 9 ，l o ，1 1 ，1 2 1 现在我们 将其演化轨道粗粒化，即像单峰映射的粗粒化那样用一个单侧无穷符号序列代表一条 轨道 以n = 1 为例。记 以o = 【。= z l x o x l a zix 0 = o 】；a i = z = x - l x o x l a ziz o = 1 】| ， 则a ou a l = a z ，即a o ，a l 构成a z 的个分割 将轨道( z ，f ( z ) ，p ( z ) ，) 粗粒化为a o ，a l ，o , 2 ，其中 毗= r 薯鬻主完： 以上称为宽度为1 的粗粒化 一般地，我们考虑宽度为死的粗粒化，定义新符号集 = ( 蜘n l 一l t a i a ，o i 船一1 ) ， 其中a o a l 一l a n 是符号集a n 中的个符号，则在小中有2 n 个不同符号现 在把俨分成下列2 n 个互不相交的既开又闭的集合； a a 。口i 咖一l = 【z a 2 i z o z l z n 一1 = o 吣q 1 口n 一1 ) ， 初等元胞自动机的复杂性研究第一章元胞自动机简介 其中a o q l 一1 a n 令z n 】= z o z l x n - - 1 ，定义粗粒化函数霸： z k ( z ) = z 叫f ( z ) f ，司f 。( z ) m ， 其中( z ) h a n ，若f ( 。) a 口。- ”则f ( z ) m = o r o o l i 鲰一l 。死的定义域为 a z ，且r ( z ) 为小上的个单侧无穷符号序列这样，轨道( z ，f ( z ) ，产( z ) ，) 被粗 粒化为x t n f ( x ) n f 2 ( z ) ，见图1 z f ( z ) p 任) n l 定义1 3 给定一个元胞自动机f ：a z a z 定义 岛= ( 矗( z ) lz a z ；晶= “( a n ) + i 劝的有限长子串，3 岛) 这里( a n ) 为有限串集合，其中每个串由a n 中的符号构成称晶中每个单侧无穷列 是宽度为的演化序列( 简称n 演化序列) ；称岛是宽度为他的演化语言，简称佗 演化语言 由上述定义可知晶由单侧无穷序列构成，而晶包含& 的所有有限子串事实 上，上面经过粗粒化后得到的演化序列与g i l m a n 等人提出的观察窗口序列是一致的， 且观察窗口宽度即为亿研究磊而不研究品的原因如下：与岛中的无限序列比较。 研究晶有很多成熟工具，具体工具将在第二章介绍 对于定义1 3 中演化语言的定义比较抽象，下面我们给出演化语言的等价定义便于 使用 首先把局部规则，推广到_ 个上t 对任意串c = c l c 2 a ，定义 f ( c ) = 又c 。c ：c 。) ，( 沈仍q ) ，( c m 一：c 仇一。c m ) ，三薹；： 其中e 为不含任何符号的空串 初等元胞自动机的复杂性研究 第一章元胞自动机简介 设c = c l c 2 ，则扩= c r n c 2 c 1 称为c 的镜象引进算子7 r ：丌c = c 2 c 3 ， c 丌= c l c 2 一1 ，其中i c l = m 表示c 的长度为m 空串的长度为0 ，即h = 0 定义1 4 设n 0 ，a i e a n ，0 i m ，则中心限制原象c p , , ( a o a l a 2 ) 定义为： c p n ( a o a l a 2 ) = s a l 一，m 一( 5 ) 一= a m a 见图2 定义1 5 设他 0 ，c i i 小，0 i m ，z a ，则中心右限制原象c r f ( a o a l 口2 ，z ) 定义为 c r p n ( a o a l a 2 ，z ) = ( s a + i 尸( s ) = 口m z ，m o ( s ) 一州= 一，) ， 其中l = 川，见图3 零霹 图2 图3 易见，当z = 时， c r p n ( a o a l a 2 a m ，z ) = c p ( a o a l o 2 ) 若c p n ( a o a l a 2 ) 毋，则串a o a l a 2 ( 小) + 出现在c a 的演化中，即 a o a l a 2 晶反之，若a o a l a 2 晶，则c p , , ( a o a l 0 2 o ，n ) o 由此可 得 定义1 6 晶= 0 因此极限语言的m e m b e r s h i p 问题一般而言不是一个平凡的问题但是对任意符号串 z a 厶则存在个自然数n 使得z 聋l n ，即有限次即可判断z 是元胞自动机的禁 止字，从而可以通过补语言来研究极限语言另一方面通过斜演化、斜周期等新工具 证明了初等元胞自动机中的2 2 号、9 4 号，1 2 2 号的极限语言都不是正规的，并且其 中1 2 2 号的极限语言不是上下文无关的 1 3 1 对极限语言的研究比较多的是对简单的元胞自动机的研究，即第1 类和第2 类初 等元胞自动机的一部分h u r d 构造了两个非初等元胞自动机，证明了它们的极限语 言都不是正规的，分别是上下文无关语言和上下文有关语言【27 _ 2 8 1 w o l f r a m 猜测对 于第3 类初等元胞自动机，除个别满映射外，其极限语言为非正规的这个猜测至今 未得到数学证明 从映射的角度出发极限语言所反映的是元胞自动机的最大不变集的复杂性这种讨 论虽然有其本身的合理性，但也有明显的局限性比如不能反映进入不变集之前的过 渡过程，其次对于满射的情况不能提供任何信息这就需要从其他方面来进行研究， 其中对演化序列和演化语言的研究就是一种方法 8 初等元胞自动机的复杂性研究 第二章形式语言与自动机 第二章形式语言与自动机 由于本文的讨论以形式语言和自动机为主要工具，本章主要介绍一些有关形式语 言与自动机的概念与有用结论这些结论与概念在本文中将直接或间接被用到所有 结论的证明在【2 9 ，3 0 】中可以查到，现从略 2 1基本概念 在本节主要介绍形式语言的记号和概念 设s 为有限个符号构成的有限集，如s = o ，1 ) ，由s 中有限个符号( 可以重复) 组成的有限长序列为s 上的个符号串( 字) ，用小写字母表示，如a 串a 中所有符 号的个数称为串的长度，记作m 如a = 1 1 0 1 1 ，则i a i = 5 不含任何符号的串称为空 串，记作毛h = 0 s 上所有有限长符号串的全体记为舻，则铲上的任意个子集 称为s 上的个形式语言 设z 和y 是舻中的两个符号串，则它们的连接x y 也是s 中的符号串若存在串 u ，u 和t o ，使得z = 删加，那么串t ，称为z 的个子串如果u = ，则称 是z 的个 前缀；如果加= ，则称t ，是z 的个后缀；如果口2 ，则称v 是z 的个真子串 定义2 1 设符号串石= a l a 2 ，称符号串矿= 1 d l 为z 的镜象对于lcs ， 称l r = z r i z 己) 为己的镜象 定义2 2 设lcs ，称f = s + 一五为工的补语言，简称补 定义2 3 设s 和a 为两个符号集，h ：s 一2 为个映射，且对每个口s ， ( 口) 都 是正规语言同时按下述方法将h 的定义域扩到伊： 1 ) 危( f ) = 7 2 ) h ( x a ) = ( z ) 九( n ) ， 其中d s ，z 9 ，称h 为一个置换 若lc 矿，我们称h ( l ) = uh ( x ) 为工的置换 x e l 若对任意的口s ， ( o ) 都是个符号串，则称h 为一个同态，h ( l ) 为l 的同 9 初等元胞自动机的复杂性研究第二章形式语言与自动机 定义2 4 设h 为个同态，即对每个8 s ，h ( a ) ，对于语言lc + ，定义 h - a ( 三) = z l ( z ) 三) 称为l 的逆同态 2 2 四类语言和四类自动机 自动机的概念在1 9 3 6 年首先由图灵提出的，他设计的自动机称为图灵机对图灵 机做某些限制或做一些改装可得到线性有界自动机、下推自动机和有限自动机它们 接收语言的能力都没有图灵机强且依次减弱 形式语言大约于1 9 5 6 年问世，c h o m s k y 从研究自然语言出发，给出一种语法的数 学模型到1 9 5 9 年，c h o m s k y 按生成语法的复杂程度将语言分成四个层次。第0 型 语言，即递归可枚举语言( r e l ) ；第1 型语言，即上下文有关语言( c , _ q l ) ；第2 型语 言，即上下文无关语言( c f l ) ；第3 型语言，即正规语言( r g l ) 它们之间的关系如 下一 r g lcc f lcc s lc r e l ， 四类语言恰好被以上提到的四类自动机所接受 下面对最简单的自动机，即有限自动机作一介绍 一个有限自动机m ，是指个五元组； m = ( q ，s 五q o ，f ) 其中q 是有限状态集，s 是有限输入符号集，口。是初始状态，而fcq 是终止状态 ( 也叫可接受状态集，q f 是不可接受状态集) ，5 ：qxs q 称为转移函数，也 就是控制状态的转移规律由于9 和s 是有限集，常用个二维表将函数表示出来 如果s 上的个串s o s l 8 n - - l 满足： 占( 6 ( 6 ( 卯，8 0 ) ，8 1 ) ，s n - 1 ) f 我们称串8 0 8 1 s n - 1 被有限自动机m 接受所有被m 接受的串组成一个语言己( m ) 1 0 初等元胞自动机的复杂性研究第二章形式语言与自动机 2 3 正规语言和上下文无关语言 正规语言可以用正规表达式写出来，我们通过正规表达式来描述正规语言先介 绍三种运算设三1 和如是符号集s 上的两个形式语言，定义l l 与l 2 的和( 即并) 为 l 1 + l 2 = z l z l 1 或z l 2 。 三l 和如的积( 即连接) 为 l x l 2 = z y i z l x ，y 三2 由此可定义语言三的幂l o = ( ) ，l = l l - i , i 1 l 的闭包运算定义为l + = u l 。 现在可以用递归的方式定义s 上的正规表达式： 1 d 是正规表达式，代表空集； 2 e 是正规表达式，代表只含空串的语言 e ) ； 3 c a 4 - 符号口s 是正规表达式，代表只含口的个串( 长度为1 ) 的语言 a ) ； 4 如果7 - 和t 是代表正规语言r 和r 的两个正规表达式，则( r4 - t ) ，( r t ) 和r 分别 代表语言r4 - 正r t 和r + 的正规表达式 正规表达式就是从口，e 和s 中的符号出发，有限次使用上述三种运算和括号。( ”， 。) ”构成的表达式，因此由 o ，1 ) 上所有串构成的语言的正规表达式为( 04 - 1 ) 关于正规表达式的重要结果是它和正规语言的等价性。每个正规语言可以用正规 表达式表示；反之，每一个正规表达式代表一个正规语言 引理2 1 正规语言类关于语言的和、连接、交，闭包、镜象、补、置换、同态和逆同 态封闭 最后我们简单介绍上下文无关语言的一些知识。它们将在第三章中用到 引理2 2 ( 上下文无关语言的泵引理) 如果工是一个上下文无关语言，则存在个只 与三有关的常数，它具有下列性质：对任何名l ，且川n ，存在石的一个分 解z = u v w x y ，使 ( 1 ) i z i l ；( 2 ) l 1 i j z i n ；( 3 ) 对每个i 0 ，使1 1 1 ) t i y l 成立 1 1 初等元胞自动机的复杂性研究第二章形式语言与自动机 泵引理是个语言为上下文无关语言的必要条件，并不是充分条件 引理2 3 上下文无关语言类关于语言的和、与正规语言的交、连接、闭包、镜象、置 换、同态和逆同态封闭 1 2 初等元胞自动机的复杂性研究 第三章1 2 6 号初等元胞自动机的演化复杂性 第三章1 2 6 号初等元胞自动机的演化复杂性 本章中我们主要研究1 2 6 号初等元胞自动机的演化语言的语法复杂性，其局部规 则定义如下： 1 1 1 ，0 0 0 _ 0 ；0 0 1 ，1 0 0 ，0 1 0 ，1 1 0 ，0 1 1 _ 1 ， ( 3 1 ) 主要结果为： 定理3 11 2 6 号初等元胞自动机的宽度大于1 的演化语言不是上下文无关语言，而是 上下文有关语言 1 2 6 号初等元胞自动机演化语言的已有结果【12 1 。 定理3 21 2 6 号初等元胞自动机的1 一演化语言是正规的 定理3 3n 2 时，1 2 6 号初等元胞自动机的n 一演化语言都不是正规语言 3 1 e 2 的限制性成员资格问题 本部分是证明定理3 1 的关键在对易的讨论中，最主要的困难是对给定的一个 串，判断它是否属于易，即易的成员资格问题本文并没有彻底解决这个问题但 在这种情况下，我们仍有可能研究易的语法层次方法就是讨论( a z ) 的一个子集， 对这个子集解决易的限制性成员资格问题 下面记a = 1 1 ，卢= 0 0 引理3 1v m 1 ，( 1 ) c 恳( p 卢) = 0 0 0 0 ；( 2 ) c 尼( “a ) = 1 0 2 m l j ( 3 ) c p 2 ( a m a ) = 0 1 2 m + 2 0 证明：由局部规则易证 根据引理3 1 ，集合( 0 0 ) + 1 1 ( o o ) 1 1c ( a 2 ) 中串的演化比较简单由( 1 1 ) 式得： ( 0 0 ) 。1 1 ( 0 0 ) m 1 1 f - a 兮c p 2 ( ( o o ) 。1 1 ( 0 0 ) m 1 1 ) d 定义3 1g ( m ) = m 凹( 1 l c p 2 ( z 口胪a ) 口，l o ) 由此定义可知t q 矿口e 2 营l 9 ( m ) ( 3 2 ) 】3 初等元胞自动机的复杂性研究 第三章1 2 6 号初等元胞自动机的演化复杂性 定义3 2 若，( 0 1 z ) = 秒，则称非空串y 为z 的斜象，定义为秒= ( z ) ，即 厶( z ) = f ( 0 1 x ) z 称为y 的斜原象若露( z ) = z ，则称z 是斜周期为p 的 定义3 3 ( z ) = m a x zl ，f2 ( z ) d ，z 0 ，z a + ) 引理3 29 ( m ) = h ( 1 m o ) 证明：由引理3 1 ( 3 ) ，c 尼( a 矿口) = 0 1 2 m + 2 0 若g 恳( 口n ) d ，则存在y l ，沈， 铆，使得f ( y i ) = 们一1 ( 2 t z ) ，且f ( y 1 ) = 0 1 2 m + 2 0 ( 如图4 ) 由局部规则( 3 1 ) 式和引理3 1 可知鼽= 6 一i 1 0 2 l b i ( 1 i z ) ，其中i b d = b l i = m ， ( 0 1 b i ) = b i 一1 ( 2 i z ) 且f ( 0 1 b 1 ) = l m 0 ，即疗。( 1 m 0 ) 谚反之若z ；- z ( 1 m 0 ) 口， 则z r l o 翻l z c p 2 ( 3 1 妒 a ) ，即c p 2 ( 妒q ) 口 综上，夕( m ) = h o m 0 ) 成立 掰1 日器目 们一气i0 0l l ： 0 0。 y l = 1 。o 。o 。j 。 l l 。 0 0 。 0 0 1 1 图4 引理3 3 2 ，圩“1 - 1 0 0 2 1 - 2 ) = 1 2 ，且当0 j f 2 i 一2 时，力( 1 0 2 - 2 ) 以0 0 结尾 此引理在【1 2 】中已证明 引理3 4v i 1 ，一1 ( 0 2 i + t - 2 ) = 1 2 州 证明：用数学归纳法证明此引理 当 = 1 时，l ( 0 0 ) = 1 1 ，结论成立 1 4 初等元胞自动机的复杂性研究 第三章1 2 6 号初等元胞自动机的演化复杂性 假设i = k 时，疗一1 ( 0 2 1 2 ) = 1 2 1 2 成立现考虑i = k + l 时的情况厶对 0 2 2 2 作用一次，结尾处0 的个数就减少2 ，故露l 1 ( 0 2 2 2 ) 以0 2 1 结尾由假设 有 一1 ( 0 2 蚌2 2 ) = 一i ( 0 2 k + i - - 2 0 2 k + i ) = 1 2 k + i - 2 0 2 1 ， f s ( 1 驴+ 1 2 0 2 。+ 1 ) ；1 0 卅1 3 1 1 0 2 + 1 一， 由引理3 3 ，詹k - - i ( 1 0 2 1 2 ) = 1 2 k + i - 1 ，且当0 歹2 k 一2 时，；( 1 0 2 1 3 1 ) 以0 1 结 尾，所以有只一1 ( 1 0 2 k + l3 1 ) = 1 2 1 。1 进一步有 只1 1 ( 0 2 2 2 ) = 力( 1 2 1 2 0 2 1 ) = 力一1 ( 1 0 2 1 一s 1 1 0 2 1 2 ) = 1 2 k + 1 。- i 一1 ( 1 0 2 1 2 ) = 1 2 k + i - 1 1 2 1 一l 一 1 妒+ 2 2 一 2 k - 1l i n e s 罴豢煮 2 k - 1 l i n e s 1 1 11 0 0 0 0 10 0 01 1 0 0 0 、l _ 。、，_ 一、_ _ _ _ 。、，_ _ - 一 o so f2 k + l 一30 8o f2 k + i 一2 01 1 1 1 1 1 11 1 1 1 、一_ _ _ 、一- _ _ 一、一_ _ _ 、一_ _ _ - ， i 8o f2 e + i 一11 so f2 k + 1 1 翻5 见图5 ，综上一1 ( 0 2 件1 2 ) = 1 计1 2 得证 引理3 5 1 ，一l ( 0 2 + z - i ) = 1 2 “- i _ 2 0 证明；由引理3 4 ，露一1 ( 0 2 件1 2 0 ) 7 r = 露一1 ( 0 2 件1 2 ) = 1 2 + 1 - - 2 对0 2 件1 ，用 作用一 次，结尾处0 的个数减少2 当厶作用一1 次时，结尾处0 的个数减少2 ( 2 一1 ) = 2 汁1 2 ，还剩1 个0 ，故一1 ( 0 2 i + 1 - i ) = 1 2 + z - 2 0 引理3 5 的证明过程可由例3 1 看出： 例3 1i = 3 时，f l ( 0 1 5 ) = 1 1 4 0 ，如图6 初等元胞自动机的复杂性研究第三章1 2 6 号初等元胞自动机的演化复杂性 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 111 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 0 1 l 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 图6 引理3 6 之2 ，当2 i m 岔+ 1 4 ，且仇为偶数时， 露一1 ( o m l ) = l m o 证明：当2 i m 2 i + 1 4 ，且m 为偶数时，0 “为0 2 件1 _ 2 的前缀由引理3 4 得 纡l 1 ( 咿1 ) 丌= 1 m 现比较o , n l 和0 m “的演化 首先考虑前缀o m 的演化，观察长度为2 的后缀，因为r e 2 i - 1 - 1 ( 0 2 - 2 0 m - 2 | + 2 ) = 1 2 i 一2 0 m - - 2 i + 2 ，且当0 歹2 扣1 1 时，力( o m ) 以0 0 结尾又因为1 2 。- 2 0 m 一2 + 2 ( 0 0 + 1 1 ) ，且，在( 0 0 + 1 1 ) 上封闭，所以当0 歹2 扣1 1 时，力( 1 2 - 2 0 m - - 2 + 2 ) 以 f j ( 1 2 - 2 0 m - - 2 t + 2 ) 为后缀，所以f ；( 1 2 - 2 0 m - - 2 + 2 ) 的后缀为0 0 或1 1 故对0 j 2 i _ 2 ， 力( 咿) 以0 0 或1 1 结尾 保持咿的2 i 一1 步演化不变，在0 m 后加符号幸在0 m 的2 一1 步演化的基础上 依次得到新串0 m 术演化的最后一个符号，设力- 1 ( o m 奉) = 1 m ! ，其中奉，兰 o ，1 ) 根 据f ( , f f l 也1 ) = + 1 和规则( 3 1 ) 式中0 0 0 0 ，0 0 1 _ 1 ，i i i _ 0 ，1 1 0 1 ， 可知当一1o i t 为0 0 或1 1 时，+ l 和+ 1 是一对应的，则木和主一对应再根据 引理3 4 中詹- 1 ( o m o ) = l m l ，得詹- 1 ( o m l ) = l m o 引理3 6 的证明过程可由例3 2 看出； 0 1 0 0 0 0 0 0 0 0 0 0 鲤0 0 111 0 0 0 0 0 0 0 哑0 0 11 0 11 0 0 0 0 0 哑0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 哑0 0 1 1 1 1 0 0 0 1 1 1 1 迦0 0 1 1 0 0 1 1 0 1 1 0 咀10 1 1 1 1 1 1 1 1 1 1 i i i 图7 0 1 0 0 0 0 0 0 0 0 0 0 0 01 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 1 1 1 1 0 0 1 0 1 1 0 0 1 1 0 1 1 0 0 1 l1 1 1 1 l l l l l l l l l o 初等元胞自动机的复杂性研究 第三章1 2 6 号初等元胞自动机的演化复杂性 例3 2t = 3 ，m = 1 2 时，( 0 1 3 ) = 1 ”，力( 0 1 2 1 ) = 1 1 2 0 ，见图7 引理3 7v i 之1 ，当2 m 2 件1 2 且m 为偶数时，h ( 1 m 0 ) 2 一1 证明：根据定义3 3 ，由引理3 5 和引理3 6 直接得出结论 引理3 8m 1 且m 为偶数时，h ( 1 m o ) l - i - m a x h ( 1 ( 0 0 1 1 ) 。0 1 ) i t = 0 ，l ，【警一1 】) 证明：设z 疗1 ( 1 m 0 ) 且满足 ( z ) = h ( 1 m 0 ) 一1 若z 以0 开头，则h ( x ) = 0 若z 以1 开头，由f ( o o o ) = f ( 1 1 1 ) = 0 可知，z 的真前缀中不能出现子串0 0 0 和 i i i ，且z 不以i i 开头，所以z 必以1 0 开头又因为i - i ( o l o ) = d ，如果z 中出现 0 1 0 ，则危( z ) = 0 故存在某个t ，使得z = 1 ( 0 0 1 1 ) 0 1 ，则危( z ) h ( 1 ( 0 0 1 1 ) t 0 1 ) 即 危( z ) _ m a x h ( 1 ( 0 0 1 1 ) 0 1 ) l t = 0 1 ，呼一1 】) 则 h ( 1 m o ) 1 - t - m a x h ( 1 ( 0 0 1 1 ) 。0 1 ) t =