有限自動機(jī)運算后的狀態(tài)最小化.pdf

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

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