最短路徑算法與正則語言的空性判定

姜盼　崔艷榮

摘要：正則語言的空性判定方法除了傳統(tǒng)的標(biāo)記法外，還有另一種方法，那就是利用最短路徑算法。通過對(duì)路徑的判斷，來證明正則語言的空性是否可判定。如果為空，則路徑無限長，不為空，則路徑是有限長的。該算法比標(biāo)記法少了標(biāo)記這一過程，減少了系統(tǒng)的開銷，提高了正則語言的判定效率。

關(guān)鍵詞：最短路徑算法 ；正則語言；可判定性

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）12-0079-02

確定型有窮自動(dòng)機(jī)能夠識(shí)別的語言稱之為正則語言。正則語言可以用有窮自動(dòng)機(jī)的形式進(jìn)行描述。本文研究算法求解問題的能力，因?yàn)橛幸恍﹩栴}算法上能夠求解，而另一些則不能[1]。我們的目的是研究算法可解性的局限。正則語言的空性問題是否是可判定的，這需要我們?nèi)プC明。

最短路徑的問題源出于交通運(yùn)輸?shù)葐栴}，對(duì)于n個(gè)城鎮(zhèn)之間的公路所組成的公路網(wǎng)，從甲地到乙地是否有公路，若有多條公路可以到達(dá)時(shí)，走哪條路最近？花費(fèi)最??？這些問題是我們最為關(guān)注的。最短路徑可以定義為從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑。解決最短路的問題有Dijkstra算法，Bellman-Ford算法，F(xiàn)loyd算法和SPFA算法等。本文結(jié)合最短路徑Dijkstra算法問題的求解來證明正則語言的空性可判定性。

1 正則語言的空性判定方法 ——標(biāo)記法

1.1 有窮自動(dòng)機(jī)（DFA）和正則語言

定義1 有窮自動(dòng)機(jī)是一個(gè)5元組（Q，Σ，Γ，δ，q0，F(xiàn)）[2]，其中：

Q：一個(gè)有窮集合，叫做狀態(tài)集。

Σ：一個(gè)有窮集合，叫做字母表。

δ：Q Σ→Q是轉(zhuǎn)移函數(shù)。

q0： 起始狀態(tài)，q0∈Q。

F：接收狀態(tài)集，F(xiàn) Q。

設(shè)M=（Q，Σ，Γ，δ，q0，F(xiàn)）是一臺(tái)有窮自動(dòng)機(jī)，ω=ω1ω2…ωn是字母表Σ上的一個(gè)字符串。如果存在*Q中的狀態(tài)序列r0，r1，…，rn，滿足下述條件：

1） r0= q0

2） δ（ri， ωi+1）=ri+1，i=0，1，…，n-1

3） rn∈F

則M接受ω。

條件（1）說機(jī)器從起始狀態(tài)開始，條件（2）說機(jī)器按照轉(zhuǎn)移函數(shù)從一個(gè)狀態(tài)到一個(gè)狀態(tài)，條件（3）說如果機(jī)器結(jié)束在接受狀態(tài)，則接受它的輸入。如果A=﹛ω|M接受ω﹜，則稱M識(shí)別語言A。

定義2如果一個(gè)語言被一臺(tái)有窮自動(dòng)機(jī)識(shí)別，則稱它是正則語言[2]。

由于當(dāng)M1對(duì)ω計(jì)算時(shí)進(jìn)入的狀態(tài)序列為

q0，q1，q1，q0，q2，q0，q0，q0，q1，q0

它滿足上述3個(gè)條件，根據(jù)計(jì)算形式定義， M1接受ω。M1的語言是

L（M1）=﹛ω|除將計(jì)數(shù)重新置0之外，ω中所有符號(hào)之和模3等于0﹜

因?yàn)镸1識(shí)別這個(gè)語言，所以它是正則語言。

1.2 圖靈機(jī)（TM）的形式定義

定義3 一個(gè)圖靈機(jī)是一個(gè)7元組（Q，Σ，Γ，δ，q0，qaccept，qreject），其中：Q，Σ，Γ都是有窮集合[3]，并且：

Q：狀態(tài)集。

Σ：輸入字母表，不包括特殊空白符號(hào) 凵。

Γ：帶字母表，其中：凵∈Γ，Σ Γ。

δ：Q ?！鶴 Γ ﹛L，R﹜是轉(zhuǎn)移函數(shù)。

q0：起始狀態(tài)，q0∈Q。

qaccept：接收狀態(tài)，qaccept∈Q。

qreject：拒絕狀態(tài)，qreject∈Q且qaccept qreject。

圖靈機(jī)M=（Q，Σ，Γ，δ，q0，qaccept，qreject）的計(jì)算方式如下：開始時(shí)，M以最左邊的n個(gè)帶方格接受輸入ω=ω1ω2…ωn∈Σ*，帶的其余部分是空白（即填以空白符）。讀寫頭從最左邊的帶方格開始運(yùn)行。注意，Σ不含空白符，故出現(xiàn)在帶上的第一個(gè)空白符表示輸入的結(jié)束。M開始運(yùn)行后，計(jì)算根據(jù)轉(zhuǎn)移函數(shù)所描述的規(guī)則進(jìn)行。如果M試圖將讀寫頭從帶的左端移出，即使轉(zhuǎn)移函數(shù)指示的是L，讀寫頭也停在原地不動(dòng)。計(jì)算一直持續(xù)到它進(jìn)入接受或拒絕狀態(tài)，此時(shí)停機(jī)。如果二者都不發(fā)生，則M永遠(yuǎn)運(yùn)行下去。

1.3 標(biāo)記法證明正則語言的空性

下面定理證明了EDFA是可判定的，因而也就證明了問題“一個(gè)給定的有窮自動(dòng)機(jī)的語言是否為空”是可判定的。

定理1 EDFA是一個(gè)可判定語言。

證明 DFA接受一個(gè)串當(dāng)且僅當(dāng)：從起始狀態(tài)出發(fā)，沿著此DFA的箭頭方向，能夠到達(dá)一個(gè)接受狀態(tài)。為檢查這個(gè)條件，設(shè)計(jì)一個(gè)使用標(biāo)記算法的TM M。

T=“對(duì)于輸入，其中A是一個(gè)DFA：

1） 標(biāo)記起始狀態(tài)。

2） 重復(fù)下列步驟， 直到所有狀態(tài)都被標(biāo)記。

3） 對(duì)于一個(gè)狀態(tài)，如果有一個(gè)到達(dá)它的轉(zhuǎn)移是從某個(gè)已經(jīng)標(biāo)記過的狀態(tài)出發(fā)的，則將其標(biāo)記。

4） 如果沒有接受狀態(tài)被標(biāo)記，則接受，否則拒絕?！?/p>

2 最短路徑算法判定正則語言的空性

2.1 最短路徑算法及其思想

Dijkstra算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)：以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止[4]。

主要思想[5]：設(shè)G=（V，E）是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示，若源頂點(diǎn)為V0，則S={V0}），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示）。對(duì)于源頂點(diǎn)V0，首先選擇其直接相鄰的頂點(diǎn)中長度最短的頂點(diǎn)Vi，那么可得從V0到Vj的最短距離為dist[j]=min{dist[j]，dist[i]+matriX[i][j]}?；谶@個(gè)原理，則可分為如下步驟：

1） 從集合U中選擇使dist[i]的值最小的頂點(diǎn)i，將i加入到S中；

2） 更新與i直接相鄰頂點(diǎn)的dist值；

3） 直到S=V結(jié)束。

2.2 最短路徑算法判定正則語言的空性

正則語言的空性判定除了標(biāo)記法證明外，還可以用最短路徑算法來證明，其過程如下：

1） 初始時(shí)，假設(shè)所有路徑權(quán)值相同。S只包含起始狀態(tài)q0，即S={ q0}，q0的距離為0。U包含除q0外的其他狀態(tài)，即：U={其余狀態(tài)}。

2） 從起始狀態(tài)q0出發(fā)，沿著此DFA的箭頭方向，在集合U中尋找其子節(jié)點(diǎn)qn，把qn加入S中（由于權(quán)值相同，子節(jié)點(diǎn)qn可能會(huì)有多個(gè)），則路徑總數(shù)為每一個(gè)深度中子節(jié)點(diǎn)總數(shù)的乘積。

3） 將子節(jié)點(diǎn)qn作為父節(jié)點(diǎn)，尋找下一個(gè)深度中的子節(jié)點(diǎn)。

4） 重復(fù)步驟（2）（3），直到需找一條有限深度的路徑。即正則語言若為空，則路徑無限長，正則語言若不為空，則路徑是有限長的。

3 結(jié)論

用最短路徑算法來證明正則語言的空性是一個(gè)比較創(chuàng)新的方法，該算法在實(shí)現(xiàn)的基礎(chǔ)上相比傳統(tǒng)正則語言的判定方法——標(biāo)記法有自己的優(yōu)勢。標(biāo)記法比較麻煩的就是要考慮每一個(gè)狀態(tài)，如果有一個(gè)到達(dá)它的轉(zhuǎn)移是從某個(gè)已經(jīng)標(biāo)記過的狀態(tài)出發(fā)的，則將其標(biāo)記。而最短路徑算法不用考慮，直接比較其深度即可。該算法提高了正則語言判定的效率，是一個(gè)比較理想的算法。

參考文獻(xiàn)：

[1] Michael Sipser. Introduction to the Theory of Computation Second Edition[M]. China Machine Press， 2007.

[2] 王曉峰.有窮自動(dòng)機(jī)狀態(tài)極小化方法及正則語言判定優(yōu)化[J].廣西民族大學(xué)學(xué)報(bào)，2008，14（3）：81-84.

[3] 趙正平.圖靈機(jī)及其構(gòu)造研究[J].電腦知識(shí)與技術(shù)，2006：192-194.

[4] 陸鋒.最短路徑算法：分類體系與研究進(jìn)展[J].測繪學(xué)報(bào)，2001，30（3）：269-275.

[5] 陳雨婕.用圖示法解析最短路徑算法[J].開發(fā)研究與設(shè)計(jì)技術(shù)，2007.