有限自動(dòng)機(jī)運(yùn)算后的狀態(tài)最小化.pdf

1、本文在自動(dòng)機(jī)理論的基礎(chǔ)上，研究了表示正則語(yǔ)言的確定型有限自動(dòng)機(jī)的最小化填表算法和確定型有限自動(dòng)機(jī)經(jīng)并、交運(yùn)算后的最小化問(wèn)題。 本文首先介紹了確定型有限自動(dòng)機(jī)的一種最小化算法-填表算法，對(duì)該算法進(jìn)行了正確性證明和計(jì)算復(fù)雜性分析。 其次，通過(guò)對(duì)該填表算法分析、研究，發(fā)現(xiàn)原算法存在的兩個(gè)問(wèn)題：一是不能處理不完全確定型有限自動(dòng)機(jī)，二是預(yù)處理過(guò)程標(biāo)記初始可區(qū)分狀態(tài)對(duì)可進(jìn)一步優(yōu)化。基于此，分別對(duì)余不可達(dá)狀態(tài)的性質(zhì)和初始標(biāo)記狀態(tài)對(duì)的本

2、質(zhì)進(jìn)行了詳細(xì)分析，進(jìn)而修改并細(xì)化原填表算法。最后對(duì)修改后的新算法進(jìn)行了正確性證明和計(jì)算復(fù)雜性分析。 隨后，通過(guò)實(shí)例進(jìn)一步從實(shí)踐上驗(yàn)證新舊填表算法的正確性，且通過(guò)觀察和比較不同自動(dòng)機(jī)在兩種算法上的運(yùn)行結(jié)果，找出了影響新舊算法運(yùn)行的4個(gè)因素，同時(shí)通過(guò)表格形式對(duì)新舊填表算法的運(yùn)行情況作一分析總結(jié)，再詳述了新算法對(duì)已有算法的5個(gè)改進(jìn)之處。 最后，基于改進(jìn)填表算法的輸入條件，對(duì)確定型有限自動(dòng)機(jī)的并、交運(yùn)算分別提出了一種合理的構(gòu)造方