语言和有限状态机离散数学讲义海南大学（共十一讲）

10.语言和有限自动机Language and FiniteState Machine10.1 语言Languages由符号以一定规则组成单词word，由单词以一定规则（语法）组成句子sentences。以一定规则给句子的含义作出解释叫语义。Grammars文法G（V，S，v0， ）短语结构文法phrase structure grammarV是有限符号集，SV，S终止符号集v0VS，初始符号，是V*上的有限产生关系product relation。w，wV*, ww是产生规则，w叫左边，w叫右边。NVS，非终止符号集。例1. S=John,Jill,drives,jogs,carelessly,rapidly,frequentlyN=sentence, noun, verbphrase,verb,adverbV=NS，v0sentence.sentencenoun verbphrasenounJohnnounJillverbphraseverb adverbverbdrivesverbjogsadverbcarelesslyadverbrapidlyadverbfrequentlysentencenoun verbphraseJill verbphraseJill verb adverbJill drives adverbJill drives frequently例2正则文法，3型文法。G=(V,S,v0,),Vv0,w,a,b,c,S=a,b,c,1 v0aw. 2. wbbw. 3. wc.G能接受的语句是v0awab2wab2nwab2nc.简记为v0ab2ncG确定的语言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简记为v0an1cbn1G能接受的语句是ancbn，n0.L(G)= ancbn | n0形式文法的分类0型文法type 0：规则无限制.无限制文法。1型文法type 1：每条规则左边的长度小于等于右边的长度。lwrlwr,上下文有关文法。2型文法type 2：A，AN，左边只含单个非终结字符。 上下文无关文法。3型文法type 3：正则文法。A或AB，A，BN，左边只含单个非终结字符，右边最右端可以有一个非终结符号。右线性文法。A或AB，A，BN，左边只含单个非终结字符，右边最右端可以有一个非终结符号。左线性文法。语言 2型文法生成的语言叫2型语言，上下文无关语言。 3型文法生成的语言叫3型语言，正则语言。 L(G)anbn|n3求文法G？L(G)=xnym|n,m2求文法G？10.2 特殊文法和语言的表示BNF 记号 notation （BachusNaur 形式）例1.sentence :nounverbphrase， noun :=John|Jill verbphrase:=verbadverb verb :=drives|jogs adverb :=carelessly|rapidly|frequently例2. v0:=aw w:=bbw|c左边记号在右边出现，叫做递归recursive例3程序设计C语言十进制数:无符号整数|十进分数| 无符号整数十进分数十进分数:=.无符号整数无符号整数:=十进数字|十进数字无符号整数十进数字:=0|1|2|3|4|5|6|7|8|923.14十进制数十进分数无符号整数十进数字2.无符号整数无符号整数无符号整数十进数字十进数字十进数字314例4.G=(V,S,identifier,)Nidentifier,remaining,digit,letterSa,b,c,z,0,1,2,，9V=NS1identifier:letter|letterremaining2remaining:letter|digit| letterremaining|digitremaining3. letter:=a|b|z4. digit:=0|1|2|3|4|5|6|7|8|9语法图Syntax Diagramsw:w1w2w3Ww1w2w3w:w1w2|w1a|bcw2Waw1w1bcw2w2w:abwWbcw:ab|abwWbbaaWba例5.v0waWbCbWbcC例6.letterletterremainingidentifierletterletterremainingidentifierletterdigitremainingbzaletter190digit正则文法和正则表达式Regular Grammar and Regular Expressions设A是一个字符集，由如下产生规则生成的字符串叫做A的正则表示, 不引起歧义时简称正则表示，省略A：Re1. 空串是正则表示。Re2. 如果,则x是正则表示。Re3. 如果，是正则表示，则，即，是正则表示。Re4. 如果，是正则表示，则()是正则表示。Re5. 如果是正则表示，则()*是正则表示。定理1. S有限集，LS*,则L正则当且仅当存在正则文法G(V,S,v0,)，LL(G)。将正则文法用BNF图表示，合成一个图，只含一个v0，其他都是终结符号，称为G的主图。通过这个图，正则文法和正则表示式有一个对应：1 终结符对应自己。2 两个片断D1和D2串连成D，D对应12。3 两个片断D1和D2并连成D，D对应12。4 一个片断D由D1的环构成，D对应1*.D1D2D1D2D1例8.acbbaCd10.3有限状态自动机FiniteState Machine有限状态集Ss0,s1,s2,sn。有限输入集I，每个xI，有一个状态转换函数fx：SS。Ffx | xI.M=（S，I，F）叫有限状态自动机。状态si，输入x，fx(si)下一个状态。M=(S, I, F)与M=（S，I，F）等价：F：SIS，F(si,x)= fx(si).例1S s0,s1, I=0,1. f0(s0)=s0，f0(s1)=s1， f1(s0)=s1，f1(s1)=s0，状态变换表： 01s0s0s1s1s1s0输入输出1输出1例2 Ia,b, S= s0,s1,s2,fa(s0)=s0，fa(s1)=s2，fa(s2)=s1，fb(s0)=s1，fb(s1)=s0，fb(s2)=s2，定义S上关系RM，siRMsj 当且仅当 存在一个输入x，fx(si)=sj.M的图：s0bs1S2bbaaaMoore Machine识别机recognition machineM(S, I, F, s0, T), s0初始状态，T可接受状态集。自动机同余和商自动机Machine Congruence and Quotient Machine设M（S，I，F），R是M上同余关系：R是S上等价关系，且对任意s，tS，sRt当且仅当对任意xI，fx(s)Rfx(t).令S/R=s | sS对任意xI，令由R是同余关系，是上的函数。令 ,称有限自动机（，I，）为M对应R的商，记做M/R.如果M(S, I, F, s0, T), R是M上的同余关系，（，I，s0，），=t | tT。称为M的商Moore Machine.例6. 令S s0, s1,s2,s3,s4, s5 ，T= s1,s3,s4.状态变换表： S上同余关系R：abs0s0s4s1s1s0s2s2s4s3s5s2s4s4s3s5s3s2 s0= s0,s2 =s2s1= s1,s3, s5=s3=s5s4s4=S/R=s0, s1, s4abs0 s0s4s1s1s0s4s4s1例7I0,1, S= s0, s1, s2, s3, s4, s5, s6, s7 ，M=S, I, FS0S4S5S2S3S6S70000111111S1000011S/R= s0, s4, s1, s2, s5, s6, s3, s7001S0S3S61S1001110.4.半群，自动机和语言semigroups，machines and languagesM=S, I, FS s0,s1,s2,sn 。F fx | xI.I*是一个独异点，空串是单位元。S上所有函数的集合SS，关于复合组成独异点，恒等变换1s是单位元。任意xI，fxSS,设wx1x2xnI*,令fwfxn fxn-1 fx1，f=1s，对每个wI*, fwSS, 称fw是w对应的状态变换函数。例1. M=S, I, F, S s0,s1,s2 , I=0,1。状态变换表F： 01s0s0s1s1s2s2s2s1s0设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 机0S0S2S100,111fw(s0)= s2，fw(s1)= s1，fw(s2)= s0.w=01011fw(s0)= s1, fw(s1)= s2, fw(s2)= s0.令M=S, I, F, 定义函数T：I*SS，对任意wI*，T(w)=fwSS。定理1. （a） T(w1w2)= T(w2) T(w1).（b） M=T(I*)构成SS的子独异点。 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)= s0fadd 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机如下图，证明fw(s0)= s0当且仅当w含有3n个1。S0S2S11110 0证明. 归纳证明性质P(n)成立： P(n):w中含1的个数为l*(w)=m，(a) m=3n, fw(s0)= s0，(b) m=3n1, fw(s0)= s1，(c) m=3n2, fw(s0)= s2。P（0）成立，设P（k）成立，m3(k+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）成立。归纳完成。因此对任意n，P(n)成立。Moore Machine识别机recognition machineM(S, I, F, s0, T), s0初始状态，TS，可接受状态集令语言 L(M)=w | wI*, fw(s0)T 。例5在例4中设T s1, fw(s0)= s1当且仅当w中含有3n1个1。L(M)wI* | w含有3n1个1。a,b例6. S=s0,s1,s2, I=a,b, T=s2aS0S2bS1ba求L(M).解：L(M)=wI*| w含有2个以上的b。10.5 自动机和正则语言定理1. 设I是一个集合，LI*. L=L(G)是3型语言，即G是3型文法，当且仅当存在一个Moore自动机M(S, I, F, s0, T), L=L(M).推论1. 设I是一个集合，LI*.存在一个Moore自动机M(S, I, F, s0, T), L=L(M) 当且仅当 L是正则集。例1设M是如下Moore机，s2是终止状态, S0S2bS1baa,ba构造正则文法G，使L(M)=L(G).解. 令I=a,b, S= s0, s1, s2,V=IS，构造G（V，I，）：s0as0 s1as1 s2as2 s1bs0bs1 s1bs2 s2bs2 s2a s2bL(M)=L(G)=a*ba*b(ab)*例2.设M是如下Moore机，s1是终止状态, S0S10011构造正则文法G，使L(M)=L(G).解. 令I=0,1, S= s0, s1,V=IS，构造G（V，I，）：s0:0s0 | 1s1 | 1s1:0s1 | 1s0 | 0s00s0 s10s1 s01s01s1 s1bs0 s10L(M)=L(G)=0*10*(10*10*)*例3. 构造一个Moore机M，使L(M)=001.解. 00S0S1S21S30S0S1S3S2S4111000,10,1例4. 令I0,1, 构造Moore机接受的输入序列w中含有10或01，即不接受全0，全1输入。S0S1S2S3S40000,10,111例5构造Moore机输入x，y，接受yy结尾的字符串。S0S1S2xyxyS0S1S2xyxyS0S1S2yyxyxx自动机的实现 例2输入0，1，可接受奇数个1的字符串。subroutine oddones(Result)1. EOIF2. ResultF3. State04. until(EOI) a. call input(x,EOI) 1. if(EOI=F)then a. if(State=0)then 1. if(x=1)then a. ResultT b. State1 belse 1. if(x=1)then a. ResultF b. State05return END of subroutine oddonessubroutine oddones(Result) version 2 1ResultFs0 2. call input(x,EOI)3. if (EOI)then a. return4. elsea. if(x=1)then 1. resultT 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. resultF 2. go to s0 b. else 1. go to s1END of subroutine oddones version 2Homework PP392-393 2, 4, 10, 20, 21, 22, 2410.6 自动机的简化令M(S, I, F, s0, T)是一个Moore自动机,定义S上一个关系：s，tS， sRt 对任意wI*, fw(s), fw(t)相容，即 fw(s)T iff fw(t)T。定理1. （a）R是S上等价关系。 （b）R是自动机同余关系。证明. (a)显然。 (b) 要证明对任意s，tS， 任意xI*, 如果sRt则fx(s)Rfx(t)。即要证明对任意wI*, fw(fx(s)T iff fw(fx(t)T。左边fwf x(s)f xw(s)右边fwf x(t)f xw(t)由题设fxw(s)T iff fxw(t)T。因此fw(fx(s)T iff fw(fx(t)T。令M/R=（，I，s0，）是M模R的商Moore机，=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, 对任意wI*, fw(s2)T, fw(s3)T.fw(s2)T 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)是一个Moore自动机, R是如上定义的等价关系M/R=（，I，s0，）是M模R的商Moore机，则L(M)=L().证明. 设wL(M)即w为M接受，fw(s0)T。w(s0)fw(s0)T/R. w为接受，wL()。L(M)L().反之，设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上关系，s，tS，sRkt 当且仅当 s,t，k相容的，即 对长度k的任意wI*, fw(s)T fw(t)T.定理3. 对任意k0，(a) Rk+1Rk.(b) Rk是等价关系.(c) RRk. 定理4. (a) S/ R0=T, ,是T的余集。(b) 对任意k0，任意s，tS， sRk1t当且仅当（1） sRkt（2） 对任意xI, fx(s)Rk fx(t).证明.长度为0的串只有，s