基于半環(huán)代數(shù)理論的有限自動(dòng)機(jī)的探討.pdf

1、在形式語言與自動(dòng)機(jī)的經(jīng)典理論中，由于所選用的數(shù)學(xué)工具的局限性，造成了證明的繁雜性，降低了證明的可讀性。本文利用半環(huán)方法來討論有限自動(dòng)機(jī)，半環(huán)方法通過有限自動(dòng)機(jī)與半環(huán)中的線性代數(shù)之間的聯(lián)系，將有限自動(dòng)機(jī)的研究轉(zhuǎn)化為半環(huán)上的線性方程的討論，使得有限自動(dòng)機(jī)的證明更加簡潔，具有更好的可讀性。主要研究內(nèi)容包括： ⑴介紹了線性代數(shù)的基礎(chǔ)知識。首先，從半環(huán)的概念特別是偏序半環(huán)引入了本文所討論的冪集半環(huán)，它是所有語言的集合。然后，逐步將半環(huán)及其

2、相關(guān)的性質(zhì)擴(kuò)展到矩陣半環(huán)上，得到冪集矩陣半環(huán)。最后，建立起冪集矩陣半環(huán)中的矩陣與有限自動(dòng)機(jī)的聯(lián)系。 ⑵介紹半環(huán)上的有限自動(dòng)機(jī)。首先，證明了半環(huán)上的有限自動(dòng)機(jī)與不確定的有限狀態(tài)自動(dòng)機(jī)識別語言的一致性。然后，用有限自動(dòng)機(jī)的半環(huán)方法來證明有限自動(dòng)機(jī)的經(jīng)典方法以及相關(guān)的結(jié)論，并且通過對比傳統(tǒng)的證明方法來對正則語言的性質(zhì)的進(jìn)行證明。 ⑶給出了半環(huán)上帶有輸出的有限自動(dòng)機(jī)。為了與傳統(tǒng)的帶有輸出的有限自動(dòng)機(jī)進(jìn)行對比，首先介紹了Moore