等價(jià)性在自動(dòng)機(jī)極小化中的應(yīng)用.pdf

1、自動(dòng)機(jī)理論的研究始于20世紀(jì)40年代，經(jīng)過幾十年的發(fā)展，自動(dòng)機(jī)理論已成為計(jì)算機(jī)科學(xué)中的一個(gè)重要分支，并應(yīng)用于計(jì)算機(jī)科學(xué)的許多領(lǐng)域，如編譯程序構(gòu)造、文本處理、結(jié)構(gòu)型數(shù)據(jù)翻譯以及開關(guān)線路設(shè)計(jì)等，它是計(jì)算機(jī)軟、硬件研究的重要基礎(chǔ)理論。 自動(dòng)機(jī)理論的研究主要涉及兩個(gè)方面，分別是正則表達(dá)式和有窮自動(dòng)機(jī)，正則表達(dá)式和有窮自動(dòng)機(jī)的描述能力是等價(jià)的，任何正則表達(dá)式都可以轉(zhuǎn)化成識(shí)別它所描述的語言的有窮自動(dòng)機(jī)。 判斷一個(gè)給定的語言是非正則語

2、言通常使用泵引理，然而，這一過程相對(duì)比較繁瑣，本文通過引入等價(jià)性原理，提出了正則語言的代數(shù)判定定理，大大簡化了正則語言的判定步驟。 有窮自動(dòng)機(jī)的化簡是一個(gè)十分重要的問題，在等價(jià)的前提下，自動(dòng)機(jī)的狀態(tài)越少，意味著越節(jié)省軟件和硬件資源。狀態(tài)的最小化過程是指將自動(dòng)機(jī)的狀態(tài)集劃分成一些不相交的子集，使得任何兩個(gè)不同的子集中的狀態(tài)都是可區(qū)分的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的。最后，可以將子集用其中一個(gè)元素代表。 本文通過等價(jià)