有限樹(shù)自動(dòng)機(jī)的一些推廣.pdf

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

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

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

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