格值正則語言及其截集性質(zhì)研究.pdf

1、自動機(jī)性質(zhì)的研究是自動機(jī)理論的中的一個重要課題。文獻(xiàn)[6,7,8]在廣泛的代數(shù)系統(tǒng)一格半群的意義下給出了一個新的自動機(jī)模型，即格值有限自動機(jī)，在格半群上研究了自動機(jī)及其接受的語言的性質(zhì)，給出了格值自動機(jī)比模糊自動機(jī)和經(jīng)典自動機(jī)具有更強(qiáng)的計算能力。因此，對格值自動機(jī)及其接受語言的性質(zhì)的研究就顯得更為重要。 本文在[6，7,8,17,19]的基礎(chǔ)上研究了格值自動機(jī)及其接受的語言的代數(shù)性質(zhì)、逼近性質(zhì)，并進(jìn)一步討論了格值正則語言截集的代

2、數(shù)性質(zhì)和逼近性質(zhì)。 自動機(jī)及其接受語言的代數(shù)性質(zhì)是指自動機(jī)及其接受語言關(guān)于交、并、補(bǔ)、閉包、反轉(zhuǎn)、同態(tài)、逆同態(tài)、商等代數(shù)運(yùn)算的封閉性。文[6，7,8]在格半群的意義下研究了格值自動機(jī)及其接受的語言的代數(shù)性質(zhì)，指出了格值正則語言關(guān)于交、并、補(bǔ)、閉包、反轉(zhuǎn)、連接、同態(tài)、逆同態(tài)等代數(shù)運(yùn)算的封閉性成立的條件，文[17，19]給出了語言或格值語言可以相互ε-逼近的概念，并給出了一些格值正則語言(NLFA)可被確定型格值正則語言(DNLFA

3、)ε-逼近的條件。 本文進(jìn)一步討論了格值正則語言的代數(shù)性質(zhì)和逼近性質(zhì)，首先給出了格值正則語言的商和可容集的概念，并證明了格值正則語言關(guān)于商是封閉的，格值語言f是格值正則的當(dāng)且僅當(dāng)f有一個可容集。然后我們給出了格值正則語言可被確定型格值正則語言ε-逼近的一些充分和必要的條件。在這些的基礎(chǔ)之上，我們研究了格值正則語言截集的性質(zhì)，給出了格值正則語言截集關(guān)于代數(shù)運(yùn)算的封閉性成立的一些條件。例如，格值正則語言截集的并、交、補(bǔ)在一般的群的意