識別幺半群直積的最少狀態(tài)DFA

黎宏偉

(宿遷學(xué)院 文理學(xué)院,江蘇 宿遷223800)

1 概述

能夠被確定有窮自動機（簡稱DFA）識別的語言稱為正規(guī)語言。文[1]定義正規(guī)語言中的乘法運算為字符串的毗連。識別正規(guī)語言的DFA一般不唯一。文[2]定義：在識別一個語言的所有DFA中，有一個初始狀態(tài)，且終結(jié)狀態(tài)最少的DFA稱為識別這個語言的最少狀態(tài)DFA。若存在正規(guī)語言到半群S的同態(tài)滿射，本文中也稱能夠識別這個正規(guī)語言的DFA可以識別半群S。文[3]證明了當每個幺半群只有一個R類時，識別這些幺半群強半格的最少狀態(tài)DFA的終結(jié)狀態(tài)的個數(shù)等于幺半群的個數(shù)。文[4]證明了識別完全單半群S=M（G；I，Λ；P）的最少狀態(tài)DFA的終結(jié)狀態(tài)的個數(shù)等于I中的元素的個數(shù)。本文中利用句法半群來證明識別兩個幺半群A1和A2的直積的最少狀態(tài)DFA的終結(jié)狀態(tài)的個數(shù)等于識別這兩個幺半群A1和A2的最少狀態(tài)DFA的終結(jié)狀態(tài)的個數(shù)的乘積。

2 預(yù)備知識

設(shè)∑為有窮字母表，令∑+表示∑上的所有非空字符串組成的集合，∑*表示∑上的所有字符串組成的集合（包括空字ε）[3]。建立在有窮字母表∑上的有限狀態(tài)自動機（Q，∑，δ，q0，F(xiàn)）是一個五元組：Q是一個有窮的狀態(tài)集合，∑是輸入字母表，q0是初始狀態(tài)且q0∈Q，F(xiàn)?Q是終結(jié)狀態(tài)集合，δ是轉(zhuǎn)移函數(shù)，它將Q×∑映射到Q，也就是說，輸入字母a，自動機由狀態(tài)q進入狀態(tài)δ（q，a）。稱自動機可以識別字符串w，若輸入w后自動機從初始狀態(tài)進入一個終結(jié)狀態(tài)。能夠被有限狀態(tài)自動機識別的語言（集合）稱為正規(guī)語言（集合）。定義∑+中字符串的運算為字符串的連接。

能夠被有窮自動機（簡稱FA）識別的語言（集合）稱為正規(guī)語言（集合）。一個FA稱為DFA，若對于字母表∑中的任一字母a和FA中的任一狀態(tài)p，從p出發(fā)標記為a的轉(zhuǎn)移至多只有一個。文[1]指出能夠被一個FA識別的語言一定能夠一個DFA識別，一個語言L是正規(guī)語言的充要條件是L能被一個FA識別，或者被一個DFA識別。

設(shè)S是半群，1是半群S之外的元，定義S1=S∪1，且對于S中的任意元s，有s?1=1?s=s。半群的R類是一種重要的代數(shù)關(guān)系。由[4]知對于半群S中的任意兩個元s和t，sRt當且僅當sS1=tS1。文[2]定義了一種特殊的等價關(guān)系，即右不變等價關(guān)系。設(shè)RL是語言L中的等價關(guān)系，x，y，z是L中的任意字符串，若xRLy?xzRLyz，則稱RL是右不變等價關(guān)系。利用右不變等價關(guān)系可以判斷語言L是否可以被一個DFA識別。

設(shè)D是A*的一個正規(guī)子集，且存在D到半群S的滿同態(tài)映射θ。設(shè)a是字母表A中的字母，若am∈D，則直接記作am∈S，而這樣的表示方式在下面的證明中不會出現(xiàn)任何矛盾。

文[3]給出了完全單半群的定義。設(shè)I和Λ是非空集合，G是幺半群，P是G上的Λ×I矩陣，在集合S=B×I×Λ上定義運算如下：

(a, i, λ )(b, j, μ ) =( ap b, i,μ)

其中P=[pλi]，pλi∈G，λ，μ∈Λ，i，j∈I，則S關(guān)于此運算構(gòu)成半群，稱為完全單半群，記作S=M（G；I，Λ；P）。本文以下設(shè)半群S是完全單半群，且Λ是有限集合。

3 引理

引理1[4]設(shè)半群S=M（G；I，Λ；P）是完全單半群，（a，i，λ），（b，j，μ）∈S則（a，i，λ）R（b，j，μ）當且僅當i=j。

由引理1顯然可以得到下面的結(jié)論:

引理2完全單半群S=M（G；I，Λ；P）中的R類的個數(shù)就等于I中的元素的個數(shù)。

引理3完全單半群S=M（G；I，Λ；P）中的R關(guān)系是右不變等價關(guān)系。

證明.由文[4]知完全單半群S=M（G；I，Λ；P）中的R關(guān)系是右同余，因此是右不變等價關(guān)系。

引理4[2]下面兩個命題是等價的：

（1）語言L∈A*被某個FA識別；

（2）L是一個右不變等價關(guān)系的并集，且這個等價關(guān)系具有有窮指數(shù)。

引理5前面所定義的完全單半群S=M（G；I，Λ；P）一定可以被某個DFA識別。

證明.設(shè)語言L∈A*且存在從L到半群S的滿同態(tài)映射。由引理2和3知半群S是有限個R類的并集。

又由引理4知R關(guān)系是右不變等價關(guān)系，因此，S是有限個右不變等價類的并集。由語言L和半群S的關(guān)系顯然可得L是有限個右不變等價類的并集。根據(jù)引理4，語言L被某個FA識別。于是L是正規(guī)語言，進而可得L被某個DFA識別。由前面的定義知半群S一定可以被某個DFA識別。

引理6[2]在同構(gòu)(即狀態(tài)重新命名)的意義下，識別一個語言的最少狀態(tài)自動機是唯一的。

引理6說明從抽象的意義上看，識別半群S的最少狀態(tài)DFA是唯一的。文[2]給出了求最少狀態(tài)DFA的方法。設(shè)M=（Q，∑，δ，q0，F(xiàn)）是識別語言L的DFA。令M'=（Q'，∑，δ'，[q0]，F(xiàn)'），其中Q'=[q]，且q是從q0可以到達的；F'={[q]，且q在F中；δ'（[q]，a）=δ'（q，a）。

引理7[2]上面構(gòu)造的自動機M'是識別語言L的最少狀態(tài)DFA。

4 結(jié)論與證明

本文主要證明一個定理

定理1設(shè)I是有限集合，識別完全單半群S=M（G；I，Λ；P）的最少終結(jié)狀態(tài)DFA的終結(jié)狀態(tài)的個數(shù)等于I中的元素的個數(shù)。

證明.定義自動機M=（Q，∑，δ，q0，I），其中q0是初始狀態(tài)，I是終結(jié)狀態(tài)集合。M識別S中字符串的方式為：若字母w=（a，i，λ），則輸入w后，自動機從初始狀態(tài)q0進入終結(jié)狀態(tài)i；在狀態(tài)i輸入字母w=（a，i，λ）后，自動機還是進入終結(jié)狀態(tài)i；在狀態(tài)i輸入字母v=（a，j，μ）后，自動機進入終結(jié)狀態(tài)j。顯然，M剛好識別半群S。由于I中的元的個數(shù)是有限個，故M是FA。下證M是DFA。

在初始狀態(tài)q0輸入字母表A中的任一字母w=（a，i，λ）后，自動機從初始狀態(tài)進入終結(jié)狀態(tài)i，且不會進入其它終結(jié)狀態(tài)。因此，從q0出發(fā)標記為w=（a，i，λ）的轉(zhuǎn)移有且只有一個。在終結(jié)狀態(tài)i輸入w=（a，i，λ）之后，自動機仍然從狀態(tài)i進入終結(jié)狀態(tài)i，且不會進入其它終結(jié)狀態(tài)。因此，從i出發(fā)標記為w=（a，i，λ）的轉(zhuǎn)移有且只有一個。由前面的定義知，在其它終結(jié)狀態(tài)j輸入字母w=（a，i，λ）后，自動機從狀態(tài)j進入終結(jié)狀態(tài)i，且不會進入其它終結(jié)狀態(tài)。因此，從其它終結(jié)狀態(tài)j出發(fā)標記為w=（a，i，λ）的轉(zhuǎn)移也是有且只有一個。綜上，在自動機M中任一狀態(tài)輸入w=（a，i，λ）之后，從這個狀態(tài)出發(fā)標記為w=（a，i，λ）的轉(zhuǎn)移至多只有一個，故M是DFA。

下面按照前面介紹的方法構(gòu)造識別半群S的最少狀態(tài)DFA。令M'=（Q'，∑，δ'，[q0]，F(xiàn)'），其中Q'=[q]，且q是自動機M中從q0可以到達的狀態(tài)；F'={[q]}，且q是自動機M中包含在I中的狀態(tài)；δ'（[q]，a）=δ（q，a）。在自動機M中從q0可以到達的狀態(tài)當然包括q0本身，另外，從q0可以到達所有的狀態(tài)I，因此Q'中的狀態(tài)數(shù)等于集合I∪{q0}中的狀態(tài)數(shù)，F(xiàn)'中的狀態(tài)數(shù)等于I中的狀態(tài)數(shù)。綜上，識別半群S的最少狀態(tài)DFA的終結(jié)狀態(tài)的個數(shù)等于I中幺半群的個數(shù)。定理1得證。

推論 從同構(gòu)的意義上看，前面定義的自動機M=（Q，∑，δ，q0，I）就是識別半群S的最少狀態(tài)DFA。