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

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

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