模糊有窮自動機與單體二階Lukasiewicz邏輯 李永明 陜西師范大學

1、模糊有窮自動機與單體二階Lukasiewicz邏輯* 國家自然科學基金(10571112), 國家重點基礎研究項目專項經(jīng)費(2002CB312200), 教育部重點研究項目(107106) 資助. 李永明1 聯(lián)系人: 李永明，陜西師范大學計算機科學學院, 西安, 710062; E-mail: liyongm; 電話:（陜西師范大學計算機科學學院, 西安, 710062）摘要：本文引入了單體二階Lukasiewicz邏輯, 進而給出了模糊有窮自動機識別語言的邏輯描述, 證明了多值邏輯意義下的Büchi與Elgot基本定理. 通過引入星-自由模糊語言與非周期

2、模糊語言, 我們完全刻畫了可以用一階Lukasiewicz邏輯定義的模糊語言.關(guān)鍵詞：模糊邏輯, 有窮自動機, 單體二階Lukasiewicz邏輯, 模糊語言, 模糊計算.1 引言形式語言在理論計算機科學研究中占有重要的地位, 對形式語言的刻畫與分類一直是其中的一個重要的研究方向. 在這個方面, 一個重要的研究成果就是Chomsky對形式語言的分類體系. 業(yè)已證明Chomsky體系的每一類語言都可以用不同的方法進行描述. 對于最基本的正則語言類, 它可以用有窮自動機來識別, 也可以用正則表達式表示, 可以用正則文法來生成, 也可以用有窮半群來刻畫等1，2. Büchi與Elgot進一

3、步建立了正則語言與單體二階邏輯可定義的語言之間的一致性, 并利用一階邏輯可定義的語言對正則語言進行了分類3，4，5. 最近, Droste與Gastin對此進行了進一步推廣, 在經(jīng)典邏輯框架下, 他們研究了形式冪級數(shù)意義下的正則語言的邏輯描述6. 經(jīng)典的形式語言是一種精確定義的語言, 它對于描述機器語言起到了重要的作用. 但在處理自然語言尤其是人類使用的語言時, 形式語言對于人類使用語言的模糊性的描述能力明顯不夠. 為此, Zadeh等人提出了模糊語言的概念, 隨后又對模糊語言進行了刻畫與分類7. 其中模糊正則語言可以用模糊有窮自動機, 模糊正則表達式, 模糊文法等刻畫8，9，10，11，12

4、，13，14. 但有關(guān)模糊正則語言在模糊邏輯意義下的邏輯描述還未有系統(tǒng)的研究結(jié)果. 模糊邏輯意義下的有窮自動機及其對應單體二階邏輯描述以及分類仍是一個待解決的問題. 本論文將在這個方面做一些研究. 我們在常用的剩余類邏輯-Lukasiewicz模糊邏輯下定義模糊有窮自動機(參見15), 以及對應的單體二階邏輯的語構(gòu)與語義, 建立了模糊邏輯意義下的Büchi與Elgot基本定理. 進一步, 我們給出可用一階Lukasiewicz邏輯定義的模糊語言, 對模糊正則語言給出了一種分類方法.2 模糊有窮自動機識別語言的有關(guān)邏輯性質(zhì)Lukasiewicz邏輯是以真值論域為的模糊邏輯 (從語義角度

5、), 其中定義為, , , . 本節(jié)主要研究Lukasiewicz邏輯意義下的有窮自動機, 我們稱為模糊有窮自動機.定義2.1. 模糊自動機是五元組, 其中為有限狀態(tài)集, 為有限字母表, 為的模糊子集, 代表初始狀態(tài)與終狀態(tài), 而為模糊轉(zhuǎn)移關(guān)系. 如下命題“為初始狀態(tài)” 記為 “”.“為終狀態(tài)” 記為 “”.“輸入使狀態(tài)轉(zhuǎn)移到” 記為 “”.這些命題的真值分別為, , . 我們用表示字母表上的有限串全體構(gòu)成的集合,表示空串. 與模糊自動機對應的上的模糊可識別謂詞定義為, 對輸入串，令, 則即命題 的真值定義為，. 稱為模糊自動機識別或接受的上的模糊語言, 也稱為上的模糊正則語言.以下記上的模糊

6、正則語言全體為, 則關(guān)于模糊并, 交, 補, 連接, Kleene閉包等封閉9，13. 而且針對Lukasiewicz邏輯, 我們還有如下結(jié)論.命題 2.1.( 9，16 )對模糊語言, 以下論斷等價.(1) .(2) 存在, 以及正則語言使得, 其中表示的特征函數(shù). (3) 存在, 及兩兩不交的正則語言使得.命題2.2. 設, 則, 其中.證明. 由命題2.1，存在，以及正則語言使得；并且存在以及正則語言使得. 這時易證，由于正則語言的交仍是正則語言，且. 因此，由命題2.1可得，. 證畢.命題2.3. 設, 則，其中， .證明. 由于，所以，其中，表示的補，定義為. 注意到 ，由命題2.2

7、知，. 另外，所以 . 證畢. 命題2.4. (13) 設 為同態(tài)，（1）若, 則 ; (2) 若滿足，對 , 且 , 則 ，其中 .3 單體二階Lukasiewicz邏輯以及它可定義的模糊語言我們首先回顧單體二階邏輯(MSO)有關(guān)概念.設為字母表, 上的MSO-邏輯公式的語構(gòu)用如下的BNF形式定義:其中,為一階變量, 而為二階集合變量. 下列公式為利用上述形式中的公式推導出的用其他連接詞表示的公式:.以下用表示公式中出現(xiàn)的全體自由變量, 用表示集合的子集全體構(gòu)成的集合.設，. 的長度為. 則字可用結(jié)構(gòu)表示，其中 .設為一階與二階變量的有限集合, ，一個 指派是一個函數(shù), 對一階變量, , 對

8、二階變量, . 若為一階變量, 規(guī)定指派為一個指派, , 而在的其余變量上與定義一致. 同理, 若為二階變量, , 同樣的可以定義指派. . 給定, 關(guān)系 按通常方式定義 (2) , 其中的定義域包含了. 明顯的, 只依賴于 .通常我們用擴展字母表來對進行表示或編碼, 即用字 表示，其中, 而定義為是一階變量且是二階變量且, 這樣的字與-指派一一對應. 以下我們就用表示這樣的字, 并稱這時的為-有效指派. 上的其他的字我們也用表示, 其中為在上的投影, 而為在上的投影, 這時稱不是有效的-指派, 以區(qū)別于-有效指派. 則語言 為有效的指派為可識別的語言, 即正則語言2. 記, . 由B

9、2;chi定理, 若 , 則下面的語言是正則語言, 記. 反之, 對上的正則語言, 一定存在MSO-句子使得.下面我們把這個結(jié)論推廣到模糊邏輯情形. 首先我們定義單體二階Lukasiewicz(簡記為LMSO)-邏輯. 對于模糊邏輯, 有兩種類型的邏輯蘊涵: 一種可以用邏輯連接詞 “”, “”, 或者 “”表示, 另一種用剩余運算定義. Lukasiewicz邏輯采用第二種方式來定義邏輯蘊涵. 因此, 在定義Lukasiewicz邏輯時, 邏輯蘊涵是一種主要的連接詞, 它不能通過其他的連接詞而定義.定義 3.1. LMSO-邏輯的公式的語構(gòu)用如下的BNF形式定義:其中, , 為一階變量, 而為

10、二階集合變量. 由此可誘導如下公式.以下用表示公式中出現(xiàn)的全體自由變量. 而用表示所有的LMSO-公式之集.定義 3.2. 設, 為有限變量集且, 則的-語義定義為上的模糊語言如下, 其中, 當不是有效的指派, 則; 否則, 歸納地定義如下:. .以下記. 注意到, 若為句子, 從而無自由變量, 則為上的模糊語言.命題 3.1. 設, , 則 .特別地, 為模糊正則語言為模糊正則語言.證明. 證明是簡單的, 只需對公式中出現(xiàn)的連接詞與量詞的個數(shù)施行歸納即可. 證畢.用表示所有的可用上的句子定義的模糊語言. 模糊邏輯意義下的Büchi-Elgot定理表述如下，這也構(gòu)成本節(jié)的主要定理.定

11、理3.1. . 證明. 由下面引理3.1，引理3.2以及引理3.3的結(jié)論得證. 引理3.1. 若 為原子的, 則.證明. 若，構(gòu)造模糊有窮自動機, , 對任意的，, , 而. 對于 的情形，經(jīng)典構(gòu)造即可,參見1. 證畢.引理3.2. 若, 且 可識別, 則, , , , 都可識別.證明. 這是因為, , , 且模糊正則語言關(guān)于并, 補, 蘊涵運算封閉. 若令 為抹去第行的投影, 即, 對, , 對, . 則, 由于模糊正則語言在投射同態(tài)下保持, 所以也是可識別的. 若將一階變量換為二階變量, 則可以證明也是可識別的. 證畢. 命題3.2. 以上構(gòu)造模糊自動機的過程是可判定的. 證明. 顯然.

12、引理3.3. 若字母表上的模糊語言是可識別的, 則存在使得為句子, 且. 證明. 由于是可識別的, 所以存在正則語言, 以及使得. 由于是正則的, 存在句子使得, 這時若令, 則易證. 實際上, 我們可以給出的具體構(gòu)造如下.設 為識別模糊語言的模糊自動機. 對 , 取集合變量, 并令, 設, 并令 , 定義公式如下:,其中, , ，也計為.這時, 對 令 表示所有滿足公式的-指派 (即)的集合, 而表示所有標記為的路徑的集合. 則存在從集合到集合的一一對應. 這是因為, 若為上的一條以為標記的路徑, 則定義-指派為, . 則易驗證. 反之, 若為-指派且, 由的定義, 構(gòu)成的一個分解, 則對任

13、意的存在唯一的使得, 且當時, 存在唯一的使得,從而得到唯一的一條路徑, 且.定義公式如下, 其中, , .這時, 若為中的一條路徑, 為對應的-指派, 則有 . 令, 這時,.另外, 明顯的, . 為了對空串輸入進行處理, 我們令, 其中, 則明顯的, . 從而若取, 則為句子, 且 . 證畢.4 可用一階Lukasiewicz邏輯定義的模糊語言這一節(jié)我們來研究可用一階Lukasiewicz邏輯定義的模糊語言. 定義 4.1. 公式稱為一階公式, 若不包含任何的集合變量, 即用表示上所有的一階公式.定義 4.2. (1) 模糊語言稱為星-自由的 (star-free), 若可通過上的有限語言

14、經(jīng)過有限次的布爾運算(并, 交, 補), 數(shù)量積, 連接運算而得到. (2)模糊語言稱為非周期的 (aperiodic), 若是可識別的且滿足條件: 存在非負整數(shù), 對任意的 , 恒有 .引理 4.1. 設為模糊語言, 則為星自由的當且僅當存在有限個以及星自由正則語言使得.證明. 設為星自由的模糊語言, 我們針對生成的運算符號個數(shù)歸納證明該引理的結(jié)論成立.當無運算符號, 這時為上的有限語言, 引理結(jié)論自然成立.設為星自由的且滿足引理條件, 則存在有限個數(shù)以及, 有限個星自由的正則語言以及使得,. 這時, 顯然滿足引理條件. 而, 其中表示語言的補語言. 從而 滿足引理條件. 對, 也滿足引理條

15、件. 關(guān)于連接運算, 我們有, 從而也滿足引理條件. 歸納的, 我們證明了若為星自由的模糊語言, 則引理的結(jié)論成立. 反之是顯然的. 證畢.引理 4.2. 設為模糊語言, 則為非周期的當且僅當存在有限個 以及非周期正則語言使得.證明. 設模糊語言為非周期的, 從而為可識別的. 由命題2.1, 存在實數(shù) 以及正則語言使得, 其中.我們證明各為非周期的語言即可. 因為為非周期的, 所以存在整數(shù)使得對任意的, 都有 . 對此, 以及,有 , 所以各都是非周期的正則語言.反之, 若滿足引理條件, 由命題2.1, 是可識別的. 因為各都是非周期的, 所以存在正整數(shù), 對任意的, 有 , 所以 , 這說明

16、為非周期的模糊語言. 證畢.引理 4.3. 對一階公式, 若為非周期的, 則也是非周期的.證明. 令, 因為為非周期的, 由引理4.2, 存在上的非周期正則語言以及實數(shù)以使得, 可以要求各 是兩兩非交的. 對, 恒有 = . 令 . 這時, 下面只要證明為非周期的正則語言即可. 我們先來證明為正則語言. 定義投影為, , 則 , . 最后一個等式成立是因為, 為有效的-指派且當且僅當存在, 使得. 這樣就證明了. 由于是上的正則語言, 且正則語言在同態(tài)下保持(17), 所以是正則語言. 下面進一步證明是非周期的即可. 由于各是非周期的, 則存在正整數(shù), 對任意的, 有 成立. 取, 我們證明

17、. 設 , , . 則 . 注意到的定義方式, 以及是非周期的, 且, 說明這個位置在對應位置的外邊, 從而由是非周期的, 可知, 由于位置在位置的外邊, 從而說明成立. 這說明是非周期的正則語言. 由引理4.2, 得是非周期的模糊語言. 證畢.定理 4.1. 設為模糊語言, 則下列條件等價.(1) 可以由一階公式表示, 即存在使得 .(2) 為星-自由的模糊語言.(3) 為非周期的模糊語言.證明. 由于星自由的正則語言與非周期的正則語言是一致的, 從而由引理4.1與引理4.2可知條件(2)與條件(3)等價.(1) (2): 設, 為一階公式, 下面針對中出現(xiàn)的連接詞與量詞個數(shù)進行歸納. 時,

18、 為原子公式, 當時, 為經(jīng)典的星自由正則語言, 從而也是星自由模糊語言, 而當時, , 后者明顯的是星自由模糊語言. 假設時命題成立, 下面考察的情況. 分以下幾種情況: (i) , 或者, 或者 , 則由星自由模糊語言的定義, 可知星自由模糊語言關(guān)于語言的并, 數(shù)量積, 連接運算封閉, 所以在這種情況下, 都有為星自由模糊語言. (ii) , 設 , , 其中, ,都是星自由的, 則為星自由的. (iii) , 則由引理4.3知是非周期的從而星自由的模糊語言.(2) (1): 因為為星-自由的模糊語言, 根據(jù)引理4.1, 存在有限個以及星自由正則語言使得. 由于各都是星自由的正則語言, 所

19、以存在一階公式使得. 令, 則明顯的, 為一階公式且. 證畢.5 結(jié)論與后續(xù)工作本文在Lukasiewicz邏輯中研究了模糊自動機以及其識別的模糊語言, 給出了單體二階Lukasiewicz邏輯的語構(gòu)與語義, 證明了模糊邏輯意義下的Büchi與Elgot定理. 通過引入星自由模糊語言和非周期模糊語言, 完全刻畫了可用一階Lukasiewicz邏輯描述的模糊語言, 給出了模糊正則語言的一種分類方法. 本文是在Lukasiewicz模糊邏輯下討論問題的, 且真值僅限于單位區(qū)間0,1, 而我們知道, 存在多種模糊邏輯體系, 而且對應的邏輯代數(shù)更為復雜, 參見18,19, 那么在不同的模糊邏

20、輯體系中本文的理論是否成立仍是需要進一步討論的問題. 另外, 模糊語言在不同的形式下的相互轉(zhuǎn)換的復雜性與模糊復雜性 20 也有待于進一步研究.參考文獻1 Khoussainov B, Nerode A. Automata Theory and its Applications, Boston: Birkäuser, 2001.2 Thomas W. Languages, automata and logic, in: G. Rozenberg, A.Salomaa (Eds.) Handbook of Formal Languages, vol. 3, Springer Verlag

21、, 1997, pp. 389-485.3 Büchi J.R. Weak second-order arithmetic and finite automata. Zeitschrifit fur Mathematische Logik and Grundlagen der Mathematik, 1960, 6: 66-92.4 Elgot C.C. Decision problems of finite automata design and related arithmetics. Transactions of the American Mathematical Socie

22、ty, 1961, 98: 21-52.5 田啟家, 沈恩紹, 史忠植. 和正則語言. 計算機學報, 1996, 19(11): 848-853. (Tian Qijia, Shen Enshao, Shi Zhongzhi. and regular language. Chinese Journal of Computer, 1996, 19(11): 848-853.)6 Droste M, Gastin P. Weighted automata and weighted logics. Theoretical Computer Science, 2007, 380: 69-86.7 Le

23、e E T, Zadeh L A. Note on fuzzy languages. Information Sciences, 1969, 1: 421-434.8 Mordeson J N, Malik D S. Fuzzy Automata and Languages: Theory and Applications. Boca Raton, London: Chapman & Hall/CRC, 2002.9 Li Y M, Pedrycz W. Fuzzy finite automata and fuzzy regular expressions with membershi

24、p values in lattice-ordered monoids. Fuzzy Sets and Systems, 2005, 156: 68-92.10 Li Y M, Pedrycz W. The equivalence between fuzzy Mealy and fuzzy Moore machines. Soft Computing, 2006,10(10): 953 - 959.11 Li Y M. Approximation and robustness of fuzzy finite automata. International Journal of Approxim

25、ate Reasoning, 2008, 47: 247-257.12 Li Y M, Pedrycz W. Minimization of lattice finite automata and its application to the decomposition of lattice languages. Fuzzy Sets and Systems, 2007, 158: 1423-1436.13 Li P, Li Y M. Algebraic properties of LA-languages. Information Sciences, 2006, 176: 3232-3255

26、.14 Ying M S. A formal model of computing with words. IEEE Transactions on Fuzzy Systems, 2002, 10(5): 640-652.15 Qiu D W. Automata theory based on complete residuated lattice-valued logic. Science in China Series F, 2001, 44(6): 419-429.16 李永明. 模糊系統(tǒng)分析. 北京: 科學出版社, 2005. (Li Yongming. Analysis of Fuz

27、zy Systems. Beijing: Academic Press, 2005.)17 Hopcroft J E, Ullman J D. Introduction to Automata Theory, Languages and Computation. New York: Addison-Wesley, 1979.18 Hajek P. Metamathematics of Fuzzy Logic. Dordrecht: Kluwer Academic Publisher, 1998.19 王國俊. 非經(jīng)典數(shù)理邏輯與近似推理. 北京: 科學出版社, 2000. (Wang Guoju

28、n. Nonstandard Mathematical Logic and Approximate Reasoning. Beijing: Academic Press, 2000.)20 Li Y M. Approximation and universality of fuzzy Turing machines. Science in China Series F, 2008, DOI: 10.1007/s11432-008-0089-y.Fuzzy Finite Automata and Monadic Second-Order Lukasiewicz LogicYongming Li(

29、College of Computer Science, Shaanxi Normal University, Xi'an, 710062, China)Abstract: We introduce monadic second-order (MSO-) Lukasiewicz logic and prove that the behaviors of fuzzy finite automata are precisely the fuzzy languages definable with sentences of our MSO Lukasiewicz logic. This ge

30、neralizes Büchi 's and Elgot's fundamental theorems to fuzzy logic setting. We also consider first-order Lukasiewicz logic and show that star-free fuzzy languages and aperiodic fuzzy languages introduced here coincide with the first-order definable ones.Keywords: Fuzzy logic, finite aut

31、omata; monadic second-order Lukasiewicz logic; fuzzy language; fuzzy computation.背景介紹Early in the history of theoretical computer science, it came to light that formal languages would be one of the foundations of further research. Therefore characterizing all languages, or even better sorting them i

32、n some hierarchy, was an important issue. For example, the regular languages can be characterized by finite automata and by regular expressions. Myhill and Nerode independently showed that this is equivalent to a characterization by finite monoids 1,2. The equivalence to monadic second-order logic i

33、s due to Büchi and Elgot, and further give a sort of regular languages definable by first-order logic 3,4. Recently, Droste and Gastin gave a further generalization to monadic second-order logic characterization of regular languages in the frame of formal power series6. Classical formal languag

34、es are precise defined languages, they are very useful in the describing of machine languages. But it is not powerful in the processing of human languages. For this, Zadeh introduced the notion of fuzzy languages and gave some characterizations in 7. For example, fuzzy regular languages can be chara

35、cterized by fuzzy finite automata, fuzzy regular expressions, fuzzy grammars 8, 9, 10, 11, 12, 13, etc. While there is no any results on the monadic second-order logic characterization of fuzzy regular languages. How to characterize fuzzy regular languages by monadic second-order logic in fuzzy setting is an open problem. We shall do some work in this way. In the frame of well-known residual-logic-Lukasiewicz fuzzy logic, we give the definition of fuzzy finite automata (see 15), and present the