有限樹自動機的一些推廣.pdf

1、自動機理論是研究離散數(shù)字系統(tǒng)的功能、結(jié)構(gòu)及其兩者關(guān)系的數(shù)學(xué)理論。它旨在研究自動機的分析與綜合問題.有限樹自動機理論是自動機理論的一個分支,隨著數(shù)字計算機、數(shù)字通信和自動化等科學(xué)技術(shù)的出現(xiàn)和發(fā)展,有限樹自動機理論在理論和實踐中發(fā)揮著越來越重要的作用。有限樹自動機的主要研究內(nèi)容與一般的自動機理論相平行,它一方面推廣了自動機已有的結(jié)果,另一方面也提出不少新問題,豐富了自動機理論的內(nèi)容。 本文以代數(shù)為工具,對偏有限樹自動機和模糊樹自動機

2、的代數(shù)結(jié)構(gòu)性質(zhì)進(jìn)行研究,并討論有限模糊樹自動機的識別語言的一些特點。 第一章為引言。這部分簡單介紹了有限自動機的應(yīng)用,闡述了本文的思路和主要內(nèi)容,并對有限樹自動機的基本概念和記號作了介紹。 第二章討論偏有限樹自動機的同態(tài)、同余、商之間的關(guān)系,主要結(jié)果有: 定理2.2.1　設(shè)A=(U,x,a,A)，B=(V,X,B) 是兩個偏有限樹自動機，U=(A,∑)，V=(B,∑),ф為A 到B的同態(tài)滿射，≡s為B 上的同余關(guān)

3、系,定義A的關(guān)系≡R:a1≡Ra2 當(dāng)且僅當(dāng)ф(a1)≡sф(a2),a1,a2∈A,則≡s為A上的同余關(guān)系且A/≡s與B/≡s同構(gòu)。 定理2.2.2　設(shè)A=(U,X.a,A)為偏有限樹自動機,U=(A,∑),若≡R,≡s 都是A上的同余關(guān)系且≡R∈≡s,則A≡s是A≡R的滿同態(tài)像。 定理2.2.3　設(shè)A=(U,X,a,A),B=(V,X,B)是兩個偏有限樹自動機,U=(A,∑),V=(B,∑),f為A到B的同態(tài)滿射,為

4、命題2.2.1中定義的上的一個同余關(guān)系。設(shè)g為A到A/≡的自然同態(tài)映射,則存在同構(gòu)映射ф:A/≡→B。 第三章將模糊自動機的同態(tài)和同余等代數(shù)結(jié)構(gòu)性質(zhì)的某些結(jié)論推廣到模糊樹自動機上.主要結(jié)果有: 定理3.1　設(shè)A為(A,∑,α,β)為L上的模糊樹自動機。若≡為A上的一個同余關(guān)系,則A與A/≡同態(tài)。 定理3.2模糊樹自動機的所有同余關(guān)系的集合作成一個完全格。 第四章討論兩個有限模糊樹自動機的同態(tài)與識別集之間的

5、關(guān)系,證明了一個有限模糊樹自動機存在狀態(tài)個數(shù)極少的商有限模糊樹自動機與之等價。并討論了有限模糊樹自動機和有限樹自動機的識別語言之間的關(guān)系,以及有限模糊樹自動機所識別的語言的一些特點.主要結(jié)果有: 定理4.1 設(shè)A=(A,∑,αA,βA),B=(B∑,αB,βB)為上的有限模糊樹自動機,若A與B同態(tài),則A與B等價。 定理4.2 對任意的有限模糊樹自動機,都存在它的商模糊樹自動機A/≡,使得A/≡的狀態(tài)個數(shù)極少且與A等價。