一類(lèi)非確定型有窮自動(dòng)機(jī)的極小化及時(shí)間復(fù)雜性.pdf

1、本文對(duì)自動(dòng)機(jī)理論的研究主要是兩個(gè)方面：自動(dòng)機(jī)的極小化和極小化的時(shí)間復(fù)雜性。在自動(dòng)機(jī)的狀態(tài)集合上定義等價(jià)關(guān)系，引入等價(jià)類(lèi)，將等價(jià)的狀態(tài)合并成一個(gè)狀態(tài)，生成新的狀態(tài)數(shù)較小的自動(dòng)機(jī)。新生成的自動(dòng)機(jī)與原自動(dòng)機(jī)識(shí)別的語(yǔ)言不變，也就是說(shuō)它們是等價(jià)的。這就是樹(shù)圖分割法的思想。利用樹(shù)圖分割法可以進(jìn)行確定型有窮自動(dòng)機(jī)的極小化。 本文的重點(diǎn)內(nèi)容是構(gòu)造了一類(lèi)非確定型有窮自動(dòng)機(jī)，即連接型有窮自動(dòng)機(jī)。這類(lèi)有窮自動(dòng)機(jī)是由兩臺(tái)確定型有窮自動(dòng)機(jī)連接而成的。利用

2、兩臺(tái)確定型有窮自動(dòng)機(jī)狀態(tài)集合上的等價(jià)關(guān)系可以構(gòu)造出連接型有窮自動(dòng)機(jī)狀態(tài)集合上的等價(jià)關(guān)系。這類(lèi)非確定型有窮自動(dòng)機(jī)也可以利用樹(shù)圖分割法來(lái)極小化。還可以得到連接后再極小化的自動(dòng)機(jī)的狀態(tài)數(shù)不大于極小化后再連接的自動(dòng)機(jī)的狀態(tài)數(shù)。非確定型有窮自動(dòng)機(jī)的情況比較復(fù)雜。往往比較大的有窮自動(dòng)機(jī)沒(méi)有等價(jià)狀態(tài)，但將其中某兩個(gè)或者幾個(gè)狀態(tài)進(jìn)行合并并不改變它們的語(yǔ)言。本文給出了非確定型有窮自動(dòng)機(jī)狀態(tài)合并的條件。找到了非確定型有窮自動(dòng)機(jī)極小化狀態(tài)的臨界條件。自動(dòng)機(jī)極