黎宏偉

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

1 概述

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

2 預(yù)備知識(shí)

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

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

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

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

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

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

其中P=[pλi]，pλi∈G，λ，μ∈Λ，i，j∈I，則S關(guān)于此運(yù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，μ）當(dāng)且僅當(dāng)i=j。

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

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

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

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

引理4[2]下面兩個(gè)命題是等價(jià)的：

（1）語(yǔ)言L∈A*被某個(gè)FA識(shí)別；

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

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

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

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

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

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

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

4 結(jié)論與證明

本文主要證明一個(gè)定理

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

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

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

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

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