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

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

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