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

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

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