|
自动机理论是研究离散数字系统的功能、结构及其两者关系的数学理论.它旨在研究自动机的分析与综合问题.有限树自动机理论是自动机理论的一个分支,随着数字计算机、数字通信和自动化等科学技术的出现和发展,有限树自动机理论在理论和实践中发挥着越来越重要的作用.有限树自动机的主要研究内容与一般的自动机理论相平行,它一方面推广了自动机已有的结果,另一方面也提出不少新问题,丰富了自动机理论的内容.本文以代数为工具,对偏有限树自动机和模糊树自动机的代数结构性质进行研究,并讨论有限模糊树自动机的识别语言的一些特点.本文分为五部分,前四部分中每个部分为一章,最后部分为结束语.第一章为引言.这部分简单介绍了有限自动机的应用,阐述了本文的思路和主要内容,并对有限树自动机的基本概念和记号作了介绍.第二章讨论偏有限树自动机的同态、同余、商之间的关系,主要结果有:定理2.2.1设Α= （U ,Χ,α, A′）,Β= （V ,Χ,β, B′）是两个偏有限树自动机, U = （ A,Σ）,V = （ B,Σ）,φ为Α到Β的同态满射,≡S为Β上的同余关系,定义A的关系≡R: a1≡Ra2当且仅当φ（ a1 ）≡Sφ（ a2）, a1 ,a2∈A,则≡R为Α上的同余关系且Α/≡R与Β/≡S同构.定理2.2.2设Α= （U ,Χ,α, A′）为偏有限树自动机, U = （ A,Σ）,若≡R,≡S都是Α上的同余关系且≡R（?）≡S,则Α/≡S是Α/≡R的满同态像.定理2.2.3设Α= （U ,Χ,α, A′）,Β= （V ,Χ,β, B′）是两个偏有限树自动机, U = （ A,Σ）,V = （ B,Σ）, f为Α到Β的同态满射,≡为命题2.2.1中定义的Α上的一个同余关系.设g为Α到Α/≡的自然同态映射,则存在同构映射φ: A/≡→B,使得下图交换:第三章将模糊自动机的同态和同余等代数结构性质的某些结论推广到模糊树自动机上.主要结果有:定理3.1设Α= （ A,Σ,δ,β）为L上的模糊树自动机.若≡为Α上的一个同余关系,则Α与Α/≡同态.定理3.2模糊树自动机的所有同余关系的集合作成一个完全格.第四章讨论两个有限模糊树自动机的同态与识别集之间的关系,证明了一个有限模糊树自动机存在状态个数极少的商有限模糊树自动机与之等价.并讨论了有限模糊树自动机和有限树自动机的识别语言之间的关系,以及有限模糊树自动机所识别的语言的一些特点.主要结果有:定理4.1设Α= （ A,Σ,δΑ,βΑ）,Β= （ B ,Σ,δΒ,βΒ）为L上的有限模糊树自动机,若Α与Β同态,则Α与Β等价.定理4.2对任意的有限模糊树自动机Α,都存在它的商模糊树自动机Α/≡,使得Α/≡的状态个数极少且与Α等价.定理4.3设（ L1 ,∧,∨）, （ L2 ,∧,∨）是两个格, f :L1→L2是格同态映射,扩展f为f : L1TΣ L2TΣ ,使得对μ∈L1TΣ ,t∈TΣ,有f （μ）（t ） = f （μ（t ））.若μ∈L1TΣ为可识别模糊集,则f（μ）∈L2TΣ是可识别的.定理4.4设L为完备分配格,μ∈LTΣ为顶拼接相容模糊集,μ（TΣ）为有限集,则对任意a∈L,μa为可识别树语言.最后部分为结束语,总结了本文的主要工作并阐述了今后的工作.
|