識別幺半群直積的最少狀態DFA

黎宏偉

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

1 概述

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

2 預備知識

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

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

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

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

文[3]給出了完全單半群的定義。設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關于此運算構成半群，稱為完全單半群，記作S=M（G；I，Λ；P）。本文以下設半群S是完全單半群，且Λ是有限集合。

3 引理

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

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

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

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

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

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

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

（2）L是一個右不變等價關系的并集，且這個等價關系具有有窮指數。

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

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

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

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

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

引理7[2]上面構造的自動機M'是識別語言L的最少狀態DFA。

4 結論與證明

本文主要證明一個定理

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

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

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

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

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