基于超級(jí)自動(dòng)機(jī)的語(yǔ)言識(shí)別及邏輯推理

摘要:該文根據(jù)自動(dòng)機(jī)的定義，對(duì)超級(jí)自動(dòng)機(jī)作了特定的定義，并給出了自動(dòng)機(jī)對(duì)語(yǔ)言的識(shí)別功能的具體步驟。接著由超級(jí)自動(dòng)機(jī)的定義，以一個(gè)特殊的例子給出了超級(jí)自動(dòng)機(jī)的語(yǔ)言識(shí)別和邏輯推理功能。

關(guān)鍵詞:自動(dòng)機(jī);超級(jí)自動(dòng)機(jī);正則式;形式語(yǔ)言

中圖分類號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)24-7033-02

Identifying Language and Solving Logic problems Based on Super Automata

YANG Meng，ZHANG Qiong-yao，SU Jiao ZHAO Miao，LI Song-song

(Comptuer Science and Technology， Huazhong Normal University， Wuhan 430079， China)

Abstract: In this paper， a specific definition of Super Automata is established based on the definition of Automata. Ten the concrete step of the automata to identify language is introduced.Finally， its function of identifying language and solving logic problems is discussed by a special example based on the definition of super automata.

Key words: automata; super automata; regular expression; formal language

美國(guó)語(yǔ)言學(xué)家N.喬姆斯基等人建立了形式文法和自動(dòng)機(jī)之間的聯(lián)系，語(yǔ)言能用后進(jìn)先出自動(dòng)機(jī)來識(shí)別這種關(guān)于形式文法與自動(dòng)機(jī)的關(guān)系，反映了語(yǔ)言的生成過程與識(shí)別過程的內(nèi)在聯(lián)系，它已成為計(jì)算機(jī)科學(xué)的基石之一，半群方法也能用于對(duì)語(yǔ)言識(shí)別的研究[5]，模糊自動(dòng)機(jī)對(duì)模糊語(yǔ)言的研究是對(duì)自動(dòng)機(jī)功能的擴(kuò)充[3]。本文進(jìn)一步討論了自動(dòng)機(jī)對(duì)語(yǔ)言的識(shí)別功能，要識(shí)別某個(gè)字符串是否是該語(yǔ)言的句子需要逐步去推導(dǎo)和規(guī)約，而推倒和規(guī)約中的回溯問題將給系統(tǒng)效率帶來極大的影響，利用有窮狀態(tài)機(jī)理論，對(duì)每個(gè)狀態(tài)和輸入都用狀態(tài)轉(zhuǎn)換圖給出來，然后根據(jù)所識(shí)別的符號(hào)串是否能走到終結(jié)狀態(tài)作為對(duì)是否屬于語(yǔ)言的判斷[2]，利用狀態(tài)轉(zhuǎn)換圖的特定用途，結(jié)合有窮自動(dòng)機(jī)理論，類似提出了具有識(shí)別自然語(yǔ)言功能和推理功能的超級(jí)有窮狀態(tài)自動(dòng)機(jī)理論，從而拓寬了自動(dòng)機(jī)識(shí)別語(yǔ)言的范圍以及解決問題的功能范圍。

1 超級(jí)有窮狀態(tài)自動(dòng)機(jī)理論

首先，根據(jù)文獻(xiàn)[1]給出有窮狀態(tài)自動(dòng)機(jī)的定義如下:

定義一:有窮狀態(tài)自動(dòng)機(jī)(FA)M是一個(gè)五元組，M=(Q， ∑，f，S，Z)，其中Q是一個(gè)有窮狀態(tài)集合，∑是一個(gè)有窮輸入字母表，f 是一個(gè)從Q*∑到Q的單值映射。f(qi，a)=qj(qi，qj∈Q，a∈∑)表示當(dāng)前狀態(tài)為qi，輸入字符為a時(shí)，自動(dòng)機(jī)將轉(zhuǎn)換到下一個(gè)狀態(tài)qj[2]。

有窮狀態(tài)自動(dòng)機(jī)中每個(gè)狀態(tài)對(duì)應(yīng)輸入的字母表只能是形式語(yǔ)言字母表，為了拓寬自動(dòng)機(jī)識(shí)別語(yǔ)言的范圍，特提出超級(jí)有窮自動(dòng)機(jī)的定義如下:

定義二:超級(jí)有窮狀態(tài)自動(dòng)機(jī)(SFA)就是超出形式語(yǔ)言的范圍，狀態(tài)可以是各種自然語(yǔ)言描述的狀態(tài)，輸入字符也擴(kuò)展到廣義各種自然語(yǔ)言的字符，不受初始狀態(tài)和末態(tài)的要求限制，其它和確定有窮狀態(tài)自動(dòng)機(jī)相仿的自動(dòng)機(jī)。

2 FA對(duì)正則語(yǔ)言的識(shí)別

語(yǔ)言可用正規(guī)文法和正規(guī)式來定義，在識(shí)別語(yǔ)言過程中，用正規(guī)文法表示的語(yǔ)言，要識(shí)別某個(gè)字符串是否是該語(yǔ)言的句子需要逐步去推導(dǎo)和規(guī)約，而推倒和規(guī)約中的回溯問題將給系統(tǒng)效率帶來極大的影響，同樣用正規(guī)集去查找是否有相符合的句子，工作量也非常大[1]，正規(guī)文法生成的語(yǔ)言等價(jià)于某種基于量子邏輯且含動(dòng)作e的自動(dòng)機(jī)[4]，下面我們以正規(guī)式為例，來構(gòu)造識(shí)別語(yǔ)言的自動(dòng)機(jī)，因?yàn)樽詣?dòng)機(jī)能快捷的識(shí)別所給句子是否屬于正規(guī)集，也就是正規(guī)語(yǔ)言。以下面的例子給出識(shí)別過程:

識(shí)別由下列正則式所對(duì)應(yīng)正則集對(duì)應(yīng)的語(yǔ)言:Example:(a|b)*(aa|bb)(a|b)*

構(gòu)造自動(dòng)機(jī)如下，任給一個(gè)字符串，我們都能根據(jù)從左至右識(shí)別字符串的一個(gè)字符，如果能走到終結(jié)狀態(tài)，則代表該字符串是該正則語(yǔ)言的句子，如果不能，則代表不是該正則語(yǔ)言的句子。

圖1中S代表起始狀態(tài)，Z代表終態(tài)，A，B，C，D，E，F(xiàn)分別代表語(yǔ)言識(shí)別過程中的中間狀態(tài)，a，b是已知的輸入字符。例如，給出字符串a(chǎn)abba，識(shí)別a到達(dá)C再識(shí)別a仍為到達(dá)C，識(shí)別b到達(dá)F，再識(shí)別b到達(dá)B，識(shí)別a到達(dá)D，D與Z等效，因而該字符串是該語(yǔ)言的句子。又如:給出字符串a(chǎn)baba，首先識(shí)別a，b到達(dá)F狀態(tài)，但由F狀態(tài)無法識(shí)別a到達(dá)終結(jié)符，因此該字符串不是該語(yǔ)言的句子。

上述就是有窮自動(dòng)機(jī)對(duì)正則語(yǔ)言的識(shí)別過程，我們可以看到，利用自動(dòng)機(jī)來識(shí)別正則語(yǔ)言非常的簡(jiǎn)潔方便，它的方便快捷使我們迫切想要擴(kuò)展它的功能，使它對(duì)語(yǔ)言的識(shí)別不僅僅局限在正則語(yǔ)言，形式語(yǔ)言，我們需要它能解決更多的問題，為此，我提出了下面的觀點(diǎn)，引出了超級(jí)有窮自動(dòng)機(jī)。

3 利用超級(jí)有窮自動(dòng)機(jī)理論識(shí)別語(yǔ)言及解決推理問題

提出超級(jí)有窮狀態(tài)自動(dòng)機(jī)理論，在于它不受輸入字符的約束，能識(shí)別的語(yǔ)

言包含各種人類自然語(yǔ)言，這樣我們就能利用它不受輸入字符的約束，不受結(jié)束狀態(tài)的限制，能識(shí)別包含各種人類自然語(yǔ)言的語(yǔ)言，因此，我們考慮利用用自動(dòng)機(jī)狀態(tài)轉(zhuǎn)移的完備性，描述人類自然語(yǔ)言的各種狀態(tài)，對(duì)自動(dòng)機(jī)而言，就是從識(shí)別語(yǔ)言的角度，利用自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換，構(gòu)造出識(shí)別各種自然語(yǔ)言的自動(dòng)機(jī)，然后利用自動(dòng)機(jī)對(duì)語(yǔ)言的識(shí)別功能，通過狀態(tài)轉(zhuǎn)換的關(guān)系，將要推導(dǎo)邏輯問題的各種狀態(tài)用自動(dòng)機(jī)表示出來，能對(duì)自然語(yǔ)言進(jìn)行識(shí)別，同時(shí)也能通過找到滿足條件的狀態(tài)及路徑達(dá)到解決推理問題的功能。超級(jí)有窮自動(dòng)機(jī)理論是對(duì)有窮自動(dòng)機(jī)理論的擴(kuò)充，它的功能較有窮自動(dòng)機(jī)更加強(qiáng)大。

1) 根據(jù)具體問題給出初始狀態(tài)的表示;

2) 找出滿足條件的和當(dāng)前狀態(tài)相關(guān)的輸入字符;

3) 根據(jù)給定的輸入字符，給出當(dāng)前狀態(tài)經(jīng)輸入字符后轉(zhuǎn)變而成的下一個(gè)狀態(tài);

4) 重復(fù)步驟2.3，直至達(dá)到終止?fàn)顟B(tài)。

以下以人，狼，白菜，羊過河問題為例進(jìn)行說明:人，狼，羊，白菜開始都在河左岸，人用船將其它三個(gè)物體都運(yùn)到河右岸，但船一次只能裝運(yùn)兩個(gè)物體，且羊，狼不能單獨(dú)留在一邊，羊和白菜也不能單獨(dú)留在一邊。人怎樣才能把他們運(yùn)過去。

結(jié)合FA對(duì)正則語(yǔ)言識(shí)別方法，我們類似的構(gòu)造自動(dòng)機(jī)，起始狀態(tài)為人，狼，羊，白菜都在河的左岸，我們用ML，SL，BL，WL表示之，此即為識(shí)別正則預(yù)言過程中的初始狀態(tài)，箭頭輸入的M，S ON THE BOAT即為人和羊 通過船渡到河的另一邊，從而狀態(tài)轉(zhuǎn)換為，人和羊在河的右岸，白菜和狼在河左岸，此即類似與輸入字符后狀態(tài)變換的過程，往后的狀態(tài)依次類推，即可得如下超級(jí)自動(dòng)機(jī)。

圖2中人狼羊白菜分別用字符M ，W，S，B表示，L表示左邊，R表示右邊XL ，XR分別表示X在河左岸和右案，X可為 M，S，B， W。X，Y ON BOAT表示X和Y在船上，X，Y可為 M，S， B，W。

利用自動(dòng)機(jī)輸入和狀態(tài)的變化即得到解決問題的路徑。例如其中路徑如下所示:開始狀態(tài)為人狼羊白菜都在左岸然后人和羊過河，從左岸到右岸，得到狀態(tài)人羊在右岸，狼白菜在左岸，接著人過河，得到狀態(tài)人，狼白菜在左岸，羊在左岸，然后人和白菜過河，得到人羊白菜在右岸，狼在左岸的狀態(tài)，然后人羊過河，得到人狼羊在左岸，白菜在右岸的狀態(tài)，再接著人和狼過河，得到人狼白菜在右岸，羊在左岸的狀態(tài)，然后人過河，得到人羊在左岸，狼白菜在右岸的狀態(tài)，然后人羊過河即得所要求得過河途徑。

以上就是自動(dòng)機(jī)對(duì)自然語(yǔ)言識(shí)別的過程，而識(shí)別的過程也正是一個(gè)邏輯推理問題解決的過程，這就充分顯示了超級(jí)有窮狀態(tài)自動(dòng)機(jī)的識(shí)別和推理功能。

4 結(jié)論

通過自動(dòng)機(jī)理論，能大大簡(jiǎn)化語(yǔ)言識(shí)別過程，用超級(jí)自動(dòng)機(jī)理論來識(shí)別自然語(yǔ)言解決邏輯推理問題是對(duì)自動(dòng)機(jī)理論的進(jìn)一步擴(kuò)充，利用超級(jí)自動(dòng)機(jī)理論能夠很大程度上增強(qiáng)自動(dòng)機(jī)的功能，識(shí)別的語(yǔ)言由形式語(yǔ)言拓展到自然語(yǔ)言，而對(duì)自然語(yǔ)言的識(shí)別又能從另一個(gè)角度簡(jiǎn)化邏輯推理問題的求解。對(duì)超級(jí)有窮自動(dòng)機(jī)的研究?jī)H從語(yǔ)言的角度對(duì)它的功能進(jìn)行了擴(kuò)充，相信從自動(dòng)機(jī)的角度，也能更進(jìn)一步拓寬超級(jí)自動(dòng)機(jī)的功能，這還有待進(jìn)一步研究。

參考文獻(xiàn):

[1] 胡倫駿，徐蘭芳，駱婷.編譯原理[M].北京:電子工業(yè)出版社，2005:38-48.

[2] 陳文宇，歐齊，陳煉.形式語(yǔ)言與自動(dòng)機(jī)[M].北京:人民郵電出版社，2005:86-90.

[3] 李永明.模糊用窮自動(dòng)機(jī)與單體二階Lukasiewicz邏輯[J].計(jì)算機(jī)學(xué)報(bào)，2008，31(10):1.

[4] 邱道文.基于量子邏輯的自動(dòng)機(jī)和文法理論[J].軟件學(xué)報(bào)，2003(1):1.

[5] 劉耀軍 徐宗本.字的組合的半群方法[J].計(jì)算機(jī)學(xué)報(bào)，2005， 28(7):1.