自然界存在著許許多多的復雜系統(tǒng)，這些系統(tǒng)的每一部分結構可以非常簡單，但由于各部分之間存在著一定的關聯(lián)（耦合），最后表現(xiàn)出的整體性態(tài)可以極其復雜。元胞自動機就是研究復雜系統(tǒng)的理想化的一種數(shù)學模型，它最早是由Von Neumann在研究生命系統(tǒng)的自我復制現(xiàn)象時提出的，后來被廣泛地用于模擬多種自然現(xiàn)象和生命現(xiàn)象。本文以形式語言理論和符號動力學為工具研究126號和122號初等元胞自動機的演化語言的復雜性。證明了：（1）126號初等元胞自動機的1-演化語言是正規(guī)的；而n-演化語言（n≥2）不是正規(guī)的。（2）122號初等元胞自動機1-演化語言是正規(guī)的；而n-演化語言（n≥2）是上下文有關語言，但不是上下文無關語言。 

【文章來源】：蘇州大學江蘇省

【文章頁數(shù)】：37 頁

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
第一章 元胞自動機簡介
    1.1 引言
    1.2 元胞自動機的定義
    1.3 元胞自動機的極限語言和演化語言
    1.4 演化語言的等價定義
第二章 形式語言與自動機
    2.1 基本概念
    2.2 四類語言和四類自動機
第三章 126號初等元胞自動機的復雜性分析
    3.1 定理3.1的證明
    3.2 定理3.2的證明
第四章 122號初等元胞自動機的復雜性分析
2的研究">    4.1 E₂的研究
    4.2 定理4.3的證明
第五章 結論和展望
參考文獻
致謝
詳細摘要


【參考文獻】：
期刊論文
[1]122號元胞自動機的演化語言復雜性[J]. 江志松.  華東理工大學學報(自然科學版). 2006(04)



本文編號：3045724