有限自動機可識別語言的基數

2018-08-01 07:45:50遲曉晴王玉涵王艷慧

計算機工程與應用 2018年15期

遲曉晴，王玉涵，王艷慧

山東科技大學數學與系統科學學院，山東青島 266590

1 引言

自動機是計算理論中最簡單的數學模型[1]。它不僅是計算機科學理論的基礎，而且與神經網絡和模型論等領域密切相關[2-3]。有限自動機在軟件工程、句法分析、形式語言和程序語言等多個領域得到了有效的應用[4-6]。由于自動機具有固定的內在狀態、記憶能力和識別判斷能力或決策能力，因此它適宜于作為一切信息系統的數學模型[7-9]。特別的，在形式語言方面，自動機提供了一種處理語言的可靠工具[10-11]。自動機可識別語言[12-14]是形式語言與自動機理論研究的一個重要領域[15-16]。

從圖論的角度講，自動機可看作一個有向圖。利用圖的鄰接矩陣可研究圖中的路及圖中任意兩個結點間的可達性等問題。對于一個字符集Σ上的有限自動機M，一個字w∈Σ*（Σ*是Σ上有限字符串的集合）可被M識別當且僅當在w的作用下，按照狀態轉移函數，自動機由初始狀態到達終止狀態。這表明，如果把自動機看作一個有向圖，可利用其鄰接矩陣，研究該自動機可識別的語言。因此，本文利用有向圖的鄰接矩陣研究有限自動機可識別語言的基數問題。

2 有向圖的鄰接矩陣

簡單回顧有向圖及其鄰接矩陣的相關知識，詳見文獻[18]。

一個圖是一個三元組 V(G),E(G),φ(G)，其中V(G)是一個非空的結點集合，E(G)是邊集合，φ(G)是從邊集合E到結點元序偶（有序偶）集合上的函數。若把圖中的邊e∈E(G )看作總是與兩個結點關聯，那么一個圖亦可簡記為G=V,E ，其中V是非空結點集，E是連接結點的邊集。若邊e與結點有序偶 vi,vj相關聯，則稱該邊為有向邊。每一條邊都是有向邊的圖稱有向圖。每一條邊都有權值的有向圖稱賦權有向圖。

根據文獻[18]中簡單圖的鄰接矩陣的定義，任意一個有向圖的鄰接矩陣的定義如下：

定義1設G=(V,E)是一個有向圖，它有n個結點V={v1,v2,…,vn}。則n階方陣A(G)或(aij)稱為G的鄰接矩陣，其中aij=k，若從vi到vj存在k條邊，k∈N0。

注1在有向圖同構的意義下，有向圖與其鄰接矩陣存在一一對應的關系，即有向圖確定時，其鄰接矩陣唯一確定，反之，鄰接矩陣確定時，其對應的有向圖唯一確定。

例1設圖G如圖1所示，其鄰接矩陣為：

圖1 有向圖G

文獻[17]中證明，若A(G )是一個簡單圖G的鄰接矩陣，則A(G)m中的i行、j列元素表示等于G中聯結vi與vj的長度為m的路的數目。下面證明此結論對任意一個有向圖的鄰接矩陣仍然成立。

引理1[18（]乘法原理）若完成一件事情要經過兩個步驟，其中第一步有n1種不同的方法，第二步有n2種不同的方法，對完成這件事情共有n1n2種方法。

定理1設A是有向圖G的鄰接矩陣，其中V={v1,v2,…,vn}，則Am中的i行、j列元素等于G中從結點vi到vj的長度為m的路的數目。

證明對m用數學歸納法。

當m=1時，由定義1可知顯然成立。

當m≥2時，假定命題對m成立，由

Am+1=Am·A故

3 有限自動機及其可識別語言

為保證本文知識的完整性，本章回顧有限自動機及其可識別語言的一些基本概念。

定義2[19]有限自動機M是一個五元組M=(Q,Σ,δ,q0,F)，其中，Q是一個非空有限集合，稱為狀態集；Σ是一個非空有限集合，稱為字符集；q0∈Q是M的初始狀態（或開始狀態）；F?Q是M終止狀態的集合；δ：Q×Σ→Q是一個映射，稱為狀態轉移函數。

對于一個有限自動機 M=(Q,Σ,δ,q0,F)，每個q∈Q稱為M 的一個狀態。若q∈F，則q是M的一個終止狀態（或接收狀態）。對任意的(q ,a)∈Q×Σ，p∈Q ，δ(q ,a)=p表示M在狀態q讀入字符a時，其狀態由q轉移到 p，即：

因此，按照結點表示狀態，邊表示遵循δ的狀態轉移，有限自動機M可以用一個賦權有向圖來表示。與M對應的賦權有向圖M′的結點集合是Q，邊集合V={(q,a,p):q,p∈Q,a∈Σ,δ(q,a)=p}。

例2給定有限自動機M=(Q ,Σ,δ,q0,F )，其中Q=(q0,q1,q2,q3)，Σ={a ,b}，F={q3}，δ：Q×Σ→Q定義為：

δ(q0,a)=q1，δ(q0,b)=q3

δ(q1,a)=q3，δ(q1,b)=q2

δ(q2,a)=q2，δ(q2,b)=q2

δ(q3,a)=q2，δ(q3,b)=q2

與M對應的賦權有向圖M′如圖2所示。

圖2 有向圖M′

若Σ是一個非空有限的字符集，則Σ*是Σ上有限個字符構成的字符串的集合，即Σ*={a1a2…an:a1,a2,…,an∈Σ,n∈N0}。這里Σ*含有空字符ε。給定一個有限自動機M=( )Q,Σ,δ,q0,F ，其狀態轉移函數δ可以誘導定義一個從Q×Σ*到Q的映射，即δ：Q×Σ*→Q，其作用法則對任意的q∈Q，w∈Σ*。

若對任意的w∈Σ*，δ(q0,w )∈F，則稱w可被自動機M識別（或接受）。

在例2中，若取q=q0，w1=abab，則：

δ(q0,a)=q1，δ(q1,b)=q2

δ(q2,a)=q2，δ(q1,a)=q3

即，在圖2中：

則δ(q0,w1)=q2?F，從而w1不能被自動機M識別。

若取 q=q0，w2=a2，則：

δ(q0,a)=q1，δ(q1,a)=q3

即，在圖2中：則δ(q0,w2)=q3∈F，從而w2可被自動機M識別。

注2 若w=a1a2…an∈Σ*被有限自動機M=(Q,Σ,δ,q0,F)識別，則在與M對應的賦權有向圖M′中存在一條由w作為權值的從q0到q(q ∈F)的路，即，其中qin=q∈F。反之，因M 與M′一一對應，故若在M′中，存在從q0到q(q ∈F)的路，即qjm，其中qjm=q，則b1b2…bm可被有限自動機M識別。給定一個有限自動機M=(Q ,Σ,δ,q0,F )，Σ*中所有可被M識別的字符串的集合稱為有限自動機M可識別的語言，記作L(M )。

例2中L(M )={b ,a2}。