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

第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？Homework PP364365 4，6，8，12，13，18，20，20，2410.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.acbbaCdHomework PP374-37510,11,12,14,23,2410.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/