语言和自动机10[1].3-10.4.doc

第10章 语言和有限自动机Language and FiniteState Machine10.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初始状态，TS，可接受状态集。例2 中， TS2, 则a*(bb)*b(ab*a)*ab* 是M可识别的语言.自动机同余和商自动机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, s7001S0S3S61S10011Homework PP380-3816, 8, 14, 18, 2010.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中含有