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

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

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