亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        有限自動(dòng)機(jī)可識(shí)別語(yǔ)言的基數(shù)

        2018-08-01 07:45:50遲曉晴王玉涵王艷慧
        關(guān)鍵詞:鄰接矩陣有向圖自動(dòng)機(jī)

        遲曉晴,王玉涵,王艷慧

        山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院,山東 青島 266590

        1 引言

        自動(dòng)機(jī)是計(jì)算理論中最簡(jiǎn)單的數(shù)學(xué)模型[1]。它不僅是計(jì)算機(jī)科學(xué)理論的基礎(chǔ),而且與神經(jīng)網(wǎng)絡(luò)和模型論等領(lǐng)域密切相關(guān)[2-3]。有限自動(dòng)機(jī)在軟件工程、句法分析、形式語(yǔ)言和程序語(yǔ)言等多個(gè)領(lǐng)域得到了有效的應(yīng)用[4-6]。由于自動(dòng)機(jī)具有固定的內(nèi)在狀態(tài)、記憶能力和識(shí)別判斷能力或決策能力,因此它適宜于作為一切信息系統(tǒng)的數(shù)學(xué)模型[7-9]。特別的,在形式語(yǔ)言方面,自動(dòng)機(jī)提供了一種處理語(yǔ)言的可靠工具[10-11]。自動(dòng)機(jī)可識(shí)別語(yǔ)言[12-14]是形式語(yǔ)言與自動(dòng)機(jī)理論研究的一個(gè)重要領(lǐng)域[15-16]。

        從圖論的角度講,自動(dòng)機(jī)可看作一個(gè)有向圖。利用圖的鄰接矩陣可研究圖中的路及圖中任意兩個(gè)結(jié)點(diǎn)間的可達(dá)性等問(wèn)題。對(duì)于一個(gè)字符集Σ上的有限自動(dòng)機(jī)M,一個(gè)字w∈Σ*(Σ*是Σ上有限字符串的集合)可被M識(shí)別當(dāng)且僅當(dāng)在w的作用下,按照狀態(tài)轉(zhuǎn)移函數(shù),自動(dòng)機(jī)由初始狀態(tài)到達(dá)終止?fàn)顟B(tài)。這表明,如果把自動(dòng)機(jī)看作一個(gè)有向圖,可利用其鄰接矩陣,研究該自動(dòng)機(jī)可識(shí)別的語(yǔ)言。因此,本文利用有向圖的鄰接矩陣研究有限自動(dòng)機(jī)可識(shí)別語(yǔ)言的基數(shù)問(wèn)題。

        2 有向圖的鄰接矩陣

        簡(jiǎn)單回顧有向圖及其鄰接矩陣的相關(guān)知識(shí),詳見文獻(xiàn)[18]。

        一個(gè)圖是一個(gè)三元組 V(G),E(G),φ(G),其中V(G)是一個(gè)非空的結(jié)點(diǎn)集合,E(G)是邊集合,φ(G)是從邊集合E到結(jié)點(diǎn)元序偶(有序偶)集合上的函數(shù)。若把圖中的邊e∈E(G )看作總是與兩個(gè)結(jié)點(diǎn)關(guān)聯(lián),那么一個(gè)圖亦可簡(jiǎn)記為G=V,E ,其中V是非空結(jié)點(diǎn)集,E是連接結(jié)點(diǎn)的邊集。若邊e與結(jié)點(diǎn)有序偶 vi,vj相關(guān)聯(lián),則稱該邊為有向邊。每一條邊都是有向邊的圖稱有向圖。每一條邊都有權(quán)值的有向圖稱賦權(quán)有向圖。

        根據(jù)文獻(xiàn)[18]中簡(jiǎn)單圖的鄰接矩陣的定義,任意一個(gè)有向圖的鄰接矩陣的定義如下:

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

        注1在有向圖同構(gòu)的意義下,有向圖與其鄰接矩陣存在一一對(duì)應(yīng)的關(guān)系,即有向圖確定時(shí),其鄰接矩陣唯一確定,反之,鄰接矩陣確定時(shí),其對(duì)應(yīng)的有向圖唯一確定。

        例1設(shè)圖G如圖1所示,其鄰接矩陣為:

        圖1 有向圖G

        文獻(xiàn)[17]中證明,若A(G )是一個(gè)簡(jiǎn)單圖G的鄰接矩陣,則A(G)m中的i行、j列元素表示等于G中聯(lián)結(jié)vi與vj的長(zhǎng)度為m的路的數(shù)目。下面證明此結(jié)論對(duì)任意一個(gè)有向圖的鄰接矩陣仍然成立。

        引理1[18(]乘法原理)若完成一件事情要經(jīng)過(guò)兩個(gè)步驟,其中第一步有n1種不同的方法,第二步有n2種不同的方法,對(duì)完成這件事情共有n1n2種方法。

        定理1設(shè)A是有向圖G的鄰接矩陣,其中V={v1,v2,…,vn},則Am中的i行、j列元素等于G中從結(jié)點(diǎn)vi到vj的長(zhǎng)度為m的路的數(shù)目。

        證明 對(duì)m用數(shù)學(xué)歸納法。

        當(dāng)m=1時(shí),由定義1可知顯然成立。

        當(dāng)m≥2時(shí),假定命題對(duì)m成立,由

        Am+1=Am·A故

        3 有限自動(dòng)機(jī)及其可識(shí)別語(yǔ)言

        為保證本文知識(shí)的完整性,本章回顧有限自動(dòng)機(jī)及其可識(shí)別語(yǔ)言的一些基本概念。

        定義2[19]有限自動(dòng)機(jī)M是一個(gè)五元組M=(Q,Σ,δ,q0,F),其中,Q是一個(gè)非空有限集合,稱為狀態(tài)集;Σ是一個(gè)非空有限集合,稱為字符集;q0∈Q是M的初始狀態(tài)(或開始狀態(tài));F?Q是M終止?fàn)顟B(tài)的集合;δ:Q×Σ→Q是一個(gè)映射,稱為狀態(tài)轉(zhuǎn)移函數(shù)。

        對(duì)于一個(gè)有限自動(dòng)機(jī) M=(Q,Σ,δ,q0,F),每個(gè)q∈Q稱為M 的一個(gè)狀態(tài)。若q∈F,則q是M的一個(gè)終止?fàn)顟B(tài)(或接收狀態(tài))。對(duì)任意的(q ,a)∈Q×Σ,p∈Q ,δ(q ,a)=p表示M在狀態(tài)q讀入字符a時(shí),其狀態(tài)由q轉(zhuǎn)移到 p,即:

        因此,按照結(jié)點(diǎn)表示狀態(tài),邊表示遵循δ的狀態(tài)轉(zhuǎn)移,有限自動(dòng)機(jī)M可以用一個(gè)賦權(quán)有向圖來(lái)表示。與M對(duì)應(yīng)的賦權(quán)有向圖M′的結(jié)點(diǎn)集合是Q,邊集合V={(q,a,p):q,p∈Q,a∈Σ,δ(q,a)=p}。

        例2給定有限自動(dòng)機(jī)M=(Q ,Σ,δ,q0,F ),其中Q=(q0,q1,q2,q3),Σ={a ,b},F(xiàn)={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對(duì)應(yīng)的賦權(quán)有向圖M′如圖2所示。

        圖2 有向圖M′

        若Σ是一個(gè)非空有限的字符集,則Σ*是Σ上有限個(gè)字符構(gòu)成的字符串的集合,即Σ*={a1a2…an:a1,a2,…,an∈Σ,n∈N0}。這里Σ*含有空字符ε。給定一個(gè)有限自動(dòng)機(jī)M=( )Q,Σ,δ,q0,F ,其狀態(tài)轉(zhuǎn)移函數(shù)δ可以誘導(dǎo)定義一個(gè)從Q×Σ*到Q的映射,即δ:Q×Σ*→Q,其作用法則對(duì)任意的q∈Q,w∈Σ*。

        若對(duì)任意的w∈Σ*,δ(q0,w )∈F,則稱w可被自動(dòng)機(jī)M識(shí)別(或接受)。

        在例2中,若取q=q0,w1=abab,則:

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

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

        即,在圖2中:

        則δ(q0,w1)=q2?F,從而w1不能被自動(dòng)機(jī)M識(shí)別。

        若取 q=q0,w2=a2,則:

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

        即,在圖2中:則δ(q0,w2)=q3∈F,從而w2可被自動(dòng)機(jī)M識(shí)別。

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

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

        4 有限自動(dòng)機(jī)可識(shí)別語(yǔ)言的基數(shù)

        利用有向圖的鄰接矩陣研究有限自動(dòng)機(jī)可識(shí)別語(yǔ)言的基數(shù)。一個(gè)集合S含有元素的個(gè)數(shù)稱為這個(gè)集合的基數(shù)(或勢(shì)),記作 ||S。

        一個(gè)有限自動(dòng)機(jī)M=( )Q,Σ,δ,q0,F ,對(duì)應(yīng)的有向圖記作M′。對(duì)任意的q∈F,Pq表示M′中從q0到q的所有路的集合。令

        由注2知,PF與L(M )一一對(duì)應(yīng),因此可得:

        命題1對(duì)于一個(gè)有限自動(dòng)機(jī) M=(Q,Σ,δ,q0,F),則 | L(M ) |=| PF|。

        一個(gè)有限自動(dòng)機(jī)M=(Q ,Σ,δ,q0,F )對(duì)應(yīng)的有向圖M′的鄰接矩陣A(M ′)是一個(gè) | Q|×|Q |的方陣,用Q標(biāo)識(shí)A(M ′)的行和列。由定理1知,對(duì)任意的q∈F,[A (M ′)]m中q0行,q列的元素表示的是M′中從q0到q的長(zhǎng)度為m的路的數(shù)目。因此:

        定理2對(duì)于一個(gè)有限自動(dòng)機(jī)M=(Q,Σ,δ,q0,F),

        例3給定一個(gè)有限自動(dòng)機(jī)M=(Q,Σ,δ,q0,F),其中Q=(q0,q1,q2,),Σ={a},F(xiàn)={q2},δ:Q×Σ→Q 定義為:

        δ(q0,a)=q1

        δ(q1,a)=q2

        δ(q2,a)=q2

        與M對(duì)應(yīng)的有向圖M′如圖3所示。

        圖3 有向圖M′

        例4自動(dòng)咖啡機(jī)M售出一杯咖啡15元,M只接受5元和10元的紙幣。在確定收到足夠的錢時(shí)它處于4種狀態(tài)q0、q1、q2、q3。M 在投入新的紙幣后改變狀態(tài),且終止?fàn)顟B(tài)只接受最終金額為15元。與M=(Q,Σ,δ,q0,F)對(duì)應(yīng)的有向圖如圖4。

        圖4 咖啡機(jī)M

        其中Q=(q0,q1,q2,q3),Σ={a ,b},F(xiàn)={q3},a和b分別表示輸入的紙幣金額為5元和10元。易知咖啡機(jī)M的鄰接矩陣為:

        從而

        兩個(gè)有限自動(dòng)機(jī)M1和M2等價(jià)當(dāng)且僅當(dāng)L(M1)=L(M2)。因此若M1和M2等價(jià),則L(M1)和L(M2)中含有長(zhǎng)度為m(m ∈N )的字的數(shù)目必相等。由定理1可得M1和M2不等價(jià)的一個(gè)充分條件。

        推論1對(duì)于兩個(gè)有限自動(dòng)機(jī)M1=(Q1,Σ,δ1,q0,F1)和M2=(Q2,Σ,δ2,q0,F2),若存在m∈N ,使得,則 M和 M不等價(jià)。12

        5 結(jié)論

        利用有向圖的鄰接矩陣給出了有限自動(dòng)機(jī)的可識(shí)別語(yǔ)言的基數(shù)公式,討論了判定兩個(gè)自動(dòng)機(jī)不等價(jià)的充分條件。這些工作將有限自動(dòng)機(jī)與矩陣聯(lián)系起來(lái),為應(yīng)用矩陣?yán)碚撎幚硪恍┳詣?dòng)機(jī)問(wèn)題奠定基礎(chǔ)。

        猜你喜歡
        鄰接矩陣有向圖自動(dòng)機(jī)
        輪圖的平衡性
        {1,3,5}-{1,4,5}問(wèn)題與鄰居自動(dòng)機(jī)
        有向圖的Roman k-控制
        一種基于模糊細(xì)胞自動(dòng)機(jī)的新型疏散模型
        超歐拉和雙有向跡的強(qiáng)積有向圖
        廣義標(biāo)準(zhǔn)自動(dòng)機(jī)及其商自動(dòng)機(jī)
        關(guān)于超歐拉的冪有向圖
        基于鄰接矩陣變型的K分網(wǎng)絡(luò)社團(tuán)算法
        一種判定的無(wú)向圖連通性的快速Warshall算法
        Inverse of Adjacency Matrix of a Graph with Matrix Weights
        亚洲日韩欧美一区二区三区| 精品人妻一区二区三区在线观看| 日本护士xxxxhd少妇| 久久精品无码一区二区三区免费 | 国产大学生粉嫩无套流白浆| 传媒在线无码| 亚洲女同精品久久女同| 91久久精品美女高潮喷白浆| 少妇高潮av久久久久久| 中文字幕乱伦视频| 国产丝袜精品不卡| 亚洲av一区二区网址| 日本午夜理论片在线观看| 风流老熟女一区二区三区| 久久久精品免费观看国产| 日本最新一区二区三区免费看| 亚洲乱妇熟女爽到高潮视频高清| av无码国产在线看免费网站| 久久久www成人免费无遮挡大片| 亚洲中文字幕巨乳人妻| 国产精品视频一区二区久久| 天天综合天天爱天天做| 一品二品三品中文字幕| 亚洲国产成人精品福利在线观看| 日韩女同一区二区三区久久| 天堂网站一区二区三区| 蜜臀av 国内精品久久久| 国内精品一区二区2021在线| 少妇特殊按摩高潮对白| www国产亚洲精品久久麻豆| 丰满老熟妇好大bbbbb| 国产v精品成人免费视频400条| 美国黄色av一区二区| 久久国产成人精品国产成人亚洲| 亚洲精品国精品久久99热一| 黄色大片一区二区中文字幕| 91久久国产香蕉熟女线看| 麻豆蜜桃av蜜臀av色欲av| 伊伊人成亚洲综合人网7777 | 凹凸世界视频a一二三| 国产成人精品无码一区二区三区|