10-語言和有限狀態(tài)機(jī)-離散數(shù)學(xué)講義-海南大學(xué)(共十一講)

1、10.語言和有限自動(dòng)機(jī)Language and FiniteState Machine§10.1 語言Languages由符號(hào)以一定規(guī)則組成單詞word，由單詞以一定規(guī)則（語法）組成句子sentences。以一定規(guī)則給句子的含義作出解釋叫語義。Grammars文法G（V，S，v0， ®）短語結(jié)構(gòu)文法phrase structure grammarV是有限符號(hào)集，SÍV，S終止符號(hào)集v0VS，初始符號(hào)，是V*上的有限產(chǎn)生關(guān)系product relation。w，wV*, ww是產(chǎn)生規(guī)則，w叫左邊，w叫右邊。NVS，非終止符號(hào)集。例1. S=John,Jill,dri

2、ves,jogs,carelessly,rapidly,frequentlyN=sentence, noun, verbphrase,verb,adverbV=NS，v0sentence.sentencenoun verbphrasenounJohnnounJillverbphraseverb adverbverbdrivesverbjogsadverbcarelesslyadverbrapidlyadverbfrequentlysentencenoun verbphraseJill verbphraseJill verb adverbJill drives adverbJill drives

3、 frequently例2正則文法，3型文法。G=(V,S,v0,),Vv0,w,a,b,c,S=a,b,c,1 v0aw. 2. wbbw. 3. wc.G能接受的語句是v0awab2wab2nwab2nc.簡記為v0Þab2ncG確定的語言L(G)= ab2nc|nNa(bb)*c.例30型文法。G=(V,S,v0,),Vv0,w,a,b,c,S=a,b,c,1. v0av0b. 2. v0bbw. 3. abwc.v0av0baav0bbanv0bnanbwbn1an1abwbn1an1cbn1簡記為v0Þan1cbn1G能接受的語句是ancbn，n0.L(G)= a

4、ncbn | n0形式文法的分類0型文法type 0：規(guī)則無限制.無限制文法。1型文法type 1：每條規(guī)則左邊的長度小于等于右邊的長度。lwrlwr,上下文有關(guān)文法。2型文法type 2：A，AN，左邊只含單個(gè)非終結(jié)字符。 上下文無關(guān)文法。3型文法type 3：正則文法。A或AB，A，BN，左邊只含單個(gè)非終結(jié)字符，右邊最右端可以有一個(gè)非終結(jié)符號(hào)。右線性文法。A或AB，A，BN，左邊只含單個(gè)非終結(jié)字符，右邊最右端可以有一個(gè)非終結(jié)符號(hào)。左線性文法。語言 2型文法生成的語言叫2型語言，上下文無關(guān)語言。 3型文法生成的語言叫3型語言，正則語言。 L(G)anbn|n3求文法G？L(G)=xnym|n

5、,m2求文法G？§10.2 特殊文法和語言的表示BNF 記號(hào) notation （BachusNaur 形式）例1.ásentenceñ :ánounñáverbphraseñ， ánounñ :=John|Jill áverbphraseñ:=áverbñáadverbñ áverbñ :=drives|jogs áadverbñ :=carelessly|rapidly|frequently例2. &#

6、225;v0ñ:=aáwñ áwñ:=bbáwñ|c左邊記號(hào)在右邊出現(xiàn)，叫做遞歸recursive例3程序設(shè)計(jì)C語言á十進(jìn)制數(shù)ñ:á無符號(hào)整數(shù)ñ|á十進(jìn)分?jǐn)?shù)ñ| á無符號(hào)整數(shù)ñá十進(jìn)分?jǐn)?shù)ñá十進(jìn)分?jǐn)?shù)ñ:=.á無符號(hào)整數(shù)ñá無符號(hào)整數(shù)ñ:=á十進(jìn)數(shù)字ñ|á十進(jìn)數(shù)字ñá無符號(hào)整數(shù)ñá十進(jìn)數(shù)字ñ

7、:=0|1|2|3|4|5|6|7|8|923.14十進(jìn)制數(shù)十進(jìn)分?jǐn)?shù)無符號(hào)整數(shù)十進(jìn)數(shù)字2.無符號(hào)整數(shù)無符號(hào)整數(shù)無符號(hào)整數(shù)十進(jìn)數(shù)字十進(jìn)數(shù)字十進(jìn)數(shù)字314例4.G=(V,S,identifier,)Nidentifier,remaining,digit,letterSa,b,c,z,0,1,2,，9V=NS1áidentifierñ:áletterñ|áletterñáremainingñ2áremainingñ:áletterñ|ádigitñ| á

8、;letterñáremainingñ|ádigitñáremainingñ3. áletterñ:=a|b|z4. ádigitñ:=0|1|2|3|4|5|6|7|8|9語法圖Syntax Diagramsáwñ:áw1ñáw2ñáw3ñWw1w2w3áwñ:áw1ñáw2ñ|áw1ña|bcáw2ñWa

9、w1w1bcw2w2áwñ:abáwñWbcáwñ:ab|abáwñWbbaaWba例5.v0waWbCbWbcC例6.letterletterremainingidentifierletterletterremainingidentifierletterdigitremainingbzaletter190digit正則文法和正則表達(dá)式Regular Grammar and Regular Expressions設(shè)A是一個(gè)字符集，由如下產(chǎn)生規(guī)則生成的字符串叫做A的正則表示, 不引起歧義時(shí)簡稱正則表示，省略A：Re1

10、. 空串是正則表示。Re2. 如果,則x是正則表示。Re3. 如果，是正則表示，則，即，是正則表示。Re4. 如果，是正則表示，則()是正則表示。Re5. 如果是正則表示，則()*是正則表示。定理1. S有限集，LÍS*,則L正則當(dāng)且僅當(dāng)存在正則文法G(V,S,v0,)，LL(G)。將正則文法用BNF圖表示，合成一個(gè)圖，只含一個(gè)v0，其他都是終結(jié)符號(hào)，稱為G的主圖。通過這個(gè)圖，正則文法和正則表示式有一個(gè)對(duì)應(yīng)：1 終結(jié)符對(duì)應(yīng)自己。2 兩個(gè)片斷D1和D2串連成D，D對(duì)應(yīng)1×2。3 兩個(gè)片斷D1和D2并連成D，D對(duì)應(yīng)12。4 一個(gè)片斷D由D1的環(huán)構(gòu)成，D對(duì)應(yīng)1*.D1D2D1D2

11、D1例8.acbbaCd§10.3有限狀態(tài)自動(dòng)機(jī)FiniteState Machine有限狀態(tài)集Ss0,s1,s2,sn。有限輸入集I，每個(gè)xI，有一個(gè)狀態(tài)轉(zhuǎn)換函數(shù)fx：SS。Ffx | xI.M=（S，I，F(xiàn)）叫有限狀態(tài)自動(dòng)機(jī)。狀態(tài)si，輸入x，fx(si)下一個(gè)狀態(tài)。M=(S, I, F)與M=（S，I，F(xiàn)）等價(jià)：F：S×IS，F(xiàn)(si,x)= fx(si).例1S s0,s1, I=0,1. f0(s0)=s0，f0(s1)=s1， f1(s0)=s1，f1(s1)=s0，狀態(tài)變換表： 01s0s0s1s1s1s0輸入輸出1輸出1例2 Ia,b, S= s0,s1,s

12、2,fa(s0)=s0，fa(s1)=s2，fa(s2)=s1，fb(s0)=s1，fb(s1)=s0，fb(s2)=s2，定義S上關(guān)系RM，siRMsj 當(dāng)且僅當(dāng) 存在一個(gè)輸入x，fx(si)=sj.M的圖：s0bs1S2bbaaaMoore Machine識(shí)別機(jī)recognition machineM(S, I, F, s0, T), s0初始狀態(tài)，T可接受狀態(tài)集。自動(dòng)機(jī)同余和商自動(dòng)機(jī)Machine Congruence and Quotient Machine設(shè)M（S，I，F(xiàn)），R是M上同余關(guān)系：R是S上等價(jià)關(guān)系，且對(duì)任意s，tS，sRt當(dāng)且僅當(dāng)對(duì)任意xI，fx(s)Rfx(t).令S/

13、R=s | sS對(duì)任意xI，令由R是同余關(guān)系，是上的函數(shù)。令 ,稱有限自動(dòng)機(jī)（，I，）為M對(duì)應(yīng)R的商，記做M/R.如果M(S, I, F, s0, T), R是M上的同余關(guān)系，（，I，s0，），=t | tT。稱為M的商Moore Machine.例6. 令S s0, s1,s2,s3,s4, s5 ，T= s1,s3,s4.狀態(tài)變換表： S上同余關(guān)系R：abs0s0s4s1s1s0s2s2s4s3s5s2s4s4s3s5s3s2 s0= s0,s2 =s2s1= s1,s3, s5=s3=s5s4s4=S/R=s0, s1, s4abs0 s0s4s1s1s0s4s4s1例7I0,1, S=

14、 s0, s1, s2, s3, s4, s5, s6, s7 ，M=S, I, FS0S4S5S2S3S6S70000111111S1000011S/R= s0, s4, s1, s2, s5, s6, s3, s7001S0S3S61S10011§10.4.半群，自動(dòng)機(jī)和語言semigroups，machines and languagesM=S, I, FS s0,s1,s2,sn 。F fx | xI.I*是一個(gè)獨(dú)異點(diǎn)，空串是單位元。S上所有函數(shù)的集合SS，關(guān)于復(fù)合組成獨(dú)異點(diǎn)，恒等變換1s是單位元。任意xI，fxSS,設(shè)wx1x2xnI*,令fwfxn fxn-1 fx1，f

15、=1s，對(duì)每個(gè)wI*, fwSS, 稱fw是w對(duì)應(yīng)的狀態(tài)變換函數(shù)。例1. M=S, I, F, S s0,s1,s2 , I=0,1。狀態(tài)變換表F： 01s0s0s1s1s2s2s2s1s0設(shè)w011I*，fw(s0)= f1 f1 f0(s0) =f1 f1 (s0) = f1(s1)= s2.fw(s1)= f1 f1 f0(s1) =f1 f1 (s2) = f1(s0)= s1.fw(s2)= f1 f1 f0(s2) =f1 f1 (s1) = f1(s2)= s0.例2上例Moor 機(jī)0S0S2S100,111fw(s0)= s2，fw(s1)= s1，fw(s2)= s0.w=0

16、1011fw(s0)= s1, fw(s1)= s2, fw(s2)= s0.令M=S, I, F, 定義函數(shù)T：I*SS，對(duì)任意wI*，T(w)=fwSS。定理1. （a） T(w1×w2)= T(w2) ×T(w1).（b） M=T(I*)構(gòu)成SS的子獨(dú)異點(diǎn)。 a例3. bS0S2S1ddb,da,b a則fadd fbad= fbadadd.證明. fadd(s0)= s0, fadd(s1)= s0, fadd(s2)= s0, fbad(s0)= s1, fbad(s1)= s1, fbad(s2)= s1, fadd fbad(s0)= fadd(s1)= s0

17、fadd fbad(s1)= fadd(s1)= s0.fadd fbad(s2)= fadd(s1)= s0.fbadadd(s0)= s0, fbadadd(s1)= s0, fbadadd(s1)= s0,因此fadd fbad= fbadadd.例4. Moor機(jī)如下圖，證明fw(s0)= s0當(dāng)且僅當(dāng)w含有3n個(gè)1。S0S2S11110 0證明. 歸納證明性質(zhì)P(n)成立： P(n):w中含1的個(gè)數(shù)為l*(w)=m，(a) m=3n, fw(s0)= s0，(b) m=3n1, fw(s0)= s1，(c) m=3n2, fw(s0)= s2。P（0）成立，設(shè)P（k）成立，m3(k+

18、1)=3k+2+1fw(s0)= fw 001(s0) = f001 fw (s0) = f001(s2)=f1(s2)=s0，m3(k+1)+1fw(s0)= fw 0*1(s0) = f0*1 fw (s0) = f0*1(s0)=f1(s0)=s1，m3(k+1)+2=3(k+1)+1+1fw(s0)=fw 10* (s0) = f10* fw (s0) = f1(s1)=f1(s1)=s2，則P（k1）成立。歸納完成。因此對(duì)任意n，P(n)成立。Moore Machine識(shí)別機(jī)recognition machineM(S, I, F, s0, T), s0初始狀態(tài)，TÍS，可

19、接受狀態(tài)集令語言 L(M)=w | wI*, fw(s0)T 。例5在例4中設(shè)T s1, fw(s0)= s1當(dāng)且僅當(dāng)w中含有3n1個(gè)1。L(M)wI* | w含有3n1個(gè)1。a,b例6. S=s0,s1,s2, I=a,b, T=s2aS0S2bS1ba求L(M).解：L(M)=wI*| w含有2個(gè)以上的b。§10.5 自動(dòng)機(jī)和正則語言定理1. 設(shè)I是一個(gè)集合，LÍI*. L=L(G)是3型語言，即G是3型文法，當(dāng)且僅當(dāng)存在一個(gè)Moore自動(dòng)機(jī)M(S, I, F, s0, T), L=L(M).推論1. 設(shè)I是一個(gè)集合，LÍI*.存在一個(gè)Moore自動(dòng)機(jī)M(S,

20、 I, F, s0, T), L=L(M) 當(dāng)且僅當(dāng) L是正則集。例1設(shè)M是如下Moore機(jī)，s2是終止?fàn)顟B(tài), S0S2bS1baa,ba構(gòu)造正則文法G，使L(M)=L(G).解. 令I(lǐng)=a,b, S= s0, s1, s2,V=IS，構(gòu)造G（V，I，）：s0as0 s1as1 s2as2 s1bs0bs1 s1bs2 s2bs2 s2a s2bL(M)=L(G)=a*ba*b(ab)*例2.設(shè)M是如下Moore機(jī)，s1是終止?fàn)顟B(tài), S0S10011構(gòu)造正則文法G，使L(M)=L(G).解. 令I(lǐng)=0,1, S= s0, s1,V=IS，構(gòu)造G（V，I，）：ás0ñ:0&#

21、225;s0ñ | 1ás1ñ | 1ás1ñ:0ás1ñ | 1ás0ñ | 0s00s0 s10s1 s01s01s1 s1bs0 s10L(M)=L(G)=0*10*(10*10*)*例3. 構(gòu)造一個(gè)Moore機(jī)M，使L(M)=001.解. 00S0S1S21S30S0S1S3S2S4111000,10,1例4. 令I(lǐng)0,1, 構(gòu)造Moore機(jī)接受的輸入序列w中含有10或01，即不接受全0，全1輸入。S0S1S2S3S40000,10,111例5構(gòu)造Moore機(jī)輸入x，y，接受yy結(jié)尾的字符串。S0

22、S1S2xyxyS0S1S2xyxyS0S1S2yyxyxx自動(dòng)機(jī)的實(shí)現(xiàn) 例2輸入0，1，可接受奇數(shù)個(gè)1的字符串。subroutine oddones(Result)1. EOI¬F2. Result¬F3. State¬04. until(EOI) a. call input(x,EOI) 1. if(EOI=F)then a. if(State=0)then 1. if(x=1)then a. Result¬T b. State¬1 belse 1. if(x=1)then a. Result¬F b. State¬05

23、return END of subroutine oddonessubroutine oddones(Result) version 2 1Result¬Fs0 2. call input(x,EOI)3. if (EOI)then a. return4. elsea. if(x=1)then 1. result¬T 2. go to s1 b. else 1. go to s0s1 5. call input(x,EOI)6. if(EOI)then a. return7. else a. if(x=1)then 1. result¬F 2. go to s0

24、b. else 1. go to s1END of subroutine oddones version 2Homework PP392-393 2, 4, 10, 20, 21, 22, 24§10.6 自動(dòng)機(jī)的簡化令M(S, I, F, s0, T)是一個(gè)Moore自動(dòng)機(jī),定義S上一個(gè)關(guān)系：s，tS， sRt Û 對(duì)任意wI*, fw(s), fw(t)相容，即 fw(s)T iff fw(t)T。定理1. （a）R是S上等價(jià)關(guān)系。 （b）R是自動(dòng)機(jī)同余關(guān)系。證明. (a)顯然。 (b) 要證明對(duì)任意s，tS， 任意xI*, 如果sRt則fx(s)Rfx(t)。即要證明

25、對(duì)任意wI*, fw(fx(s)T iff fw(fx(t)T。左邊f(xié)wf x(s)f xw(s)右邊f(xié)wf x(t)f xw(t)由題設(shè)fxw(s)T iff fxw(t)T。因此fw(fx(s)T iff fw(fx(t)T。令M/R=（，I，s0，）是M模R的商Moore機(jī)，=S/R，T/R.令Ss0,s1, s2,s3, I=0,1, T= s2,s3, M=(S, I, F, s0, T). S0S2S1S300001111s0Rs1, fw(s0)T Ûw含有1 Û fw(s1)T.s2Rs3, 對(duì)任意wI*, fw(s2)T, fw(s3)T.fw(s2)T

26、Û fw(s3)T.s0= s0, s1, s2= s2, s3, S/R=s0, s2, T/R=s2, S0S200,11定理2. 令M(S, I, F, s0, T)是一個(gè)Moore自動(dòng)機(jī), R是如上定義的等價(jià)關(guān)系M/R=（，I，s0，）是M模R的商Moore機(jī)，則L(M)=L().證明. 設(shè)wL(M)即w為M接受，fw(s0)T。w(s0)fw(s0)T/R. w為接受，wL()。L(M)ÍL().反之，設(shè)wL()即w為接受，w(s0)fw(s0)T /R. 存在tT, tRfw(s0)，tf(t)f(fw(s0)fw(s0)T，wL(M). L()ÍL(M).因此L(M)=L().令Rk是S上關(guān)系，s，tS，sRkt 當(dāng)且僅當(dāng) s,t，k相容的，即 對(duì)長度k的任意wI*, fw(s)T Û fw(t)T.定理3. 對(duì)任意k0，(a) Rk+1ÍRk.(b) Rk是等價(jià)關(guān)系.(c) RÍRk. 定理4. (a) S/ R0=T, ,是T的余