基于等價類的非確定有窮自動機最小化方法的研究.pdf

1、有窮自動理論給出了一類計算模型，這種模型在計算機科學的若干應用領域都有著重要的作用。有窮自動機可以是確定型有窮自動機(DFA)或非確定型有窮自動機(NFA)，識別的語言類稱為正則語言。有窮自動機的最小化是一個十分重要的問題。這里所說的最小化是指在等價的前提下，對有窮自動機進行轉換，使得經(jīng)轉換所得到的有窮自動機狀態(tài)結點最少，但它仍然與原來有窮自動機等價。一般來說，自動機的狀態(tài)結點越少，意味著越節(jié)省軟件和硬件資源，實現(xiàn)它的程序也越簡練。

2、 本文主要研究和探索基于等價類的非確定型有窮自動機的最小化。主要研究內容包括以下三個方面： (1)關于有窮自動機與正則語言的關系介紹了有窮自動機的基礎知識，正則語言的性質以及引入狀態(tài)轉換圖的概念證明有窮自動機和正則表達式的等價性。 (2)基于等價類的確定型有窮自動機最小化算法的分析研究了確定型有窮自動機和非確定型有窮自動機的等價性，并在確定型有窮自動機的狀態(tài)集上引入等價關系，給出了等價類的算法，利用該算法將自動機生成