10-语言和有限状态机-离散数学讲义-海南大学(共十一讲).doc

10.语言和有限自动机 Language and Finite－State Machine §10.1 语言Languages 由符号以一定规则组成单词word， 由单词以一定规则（语法）组成句子sentences。 以一定规则给句子的含义作出解释叫语义。 Grammars文法 G＝（V，S，v0， (）短语结构文法phrase structure grammar V是有限符号集， S(V，S终止符号集 v0∈V－S，初始符号， →是V*上的有限产生关系product relation。 w，w’∈V*, w→w’是产生规则， w叫左边，w’叫右边。  N＝V－S，非终止符号集。 例1. S={John,Jill,drives,jogs,carelessly, rapidly,frequently} N={sentence, noun, verbphrase,verb, adverb} V=N∪S，v0＝sentence. sentence→noun verbphrase noun→John noun→Jill verbphrase→verb adverb verb→drives verb→jogs adverb→carelessly adverb→rapidly adverb→frequently sentence noun verbphrase Jill verbphrase Jill verb adverb Jill drives adverb Jill drives frequently 例2．正则文法，3型文法。 G=(V,S,v0,→), V＝{v0,w,a,b,c},S={a,b,c}, v0→aw. 2. w→bbw. 3. w→c. G能接受的语句是 v0→aw→ab2w→……→ab2nw→ab2nc. 简记为v0(ab2nc G确定的语言L(G)={ ab2nc|n∈N}＝a(bb)*c. 例3．0型文法。 G=(V,S,v0,→), V＝{v0,w,a,b,c},S={a,b,c}, 1. v0→av0b. 2. v0b→bw. 3. abw→c. v0→av0b→aav0bb→anv0bn→anbwbn－1 ＝an－1abwbn－1→an－1cbn－1 简记为v0(an－1cbn－1 G能接受的语句是ancbn，n≥0. L(G)={ ancbn | n≥0} 形式文法的分类 0型文法type 0： 规则无限制.无限制文法。 1型文法type 1： 每条规则左边的长度小于等于右边的长度。 lwr→lw’r,上下文有关文法。 2型文法type 2： A→α，A∈N，左边只含单个非终结字符。 上下文无关文法。 3型文法type 3：正则文法。 A→α或A→αB，A，B∈N，左边只含单个非终结字符，右边最右端可以有一个非终结符号。右线性文法。 A→α或A→Bα，A，B∈N，左边只含单个非终结字符，右边最右端可以有一个非终结符号。左线性文法。 语言 2型文法生成的语言叫2型语言，上下文无关语言。 3型文法生成的语言叫3型语言，正则语言。 L(G)＝{anbn|n≥3} 求文法G？ L(G)={xnym|n,m≥2} 求文法G？ §10.2 特殊文法和语言的表示 BNF 记号 notation （Bachus－Naur 形式） 例1.(sentence( ::＝(noun((verbphrase(， (noun( ::=John|Jill (verbphrase(::=(verb((adverb( (verb( ::=drives|jogs (adverb( ::=carelessly|rapidly|frequently 例2. (v0(::=a(w( (w(::=bb(w(|c 左边记号在右边出现，叫做递归recursive 例3．程序设计C语言 (十进制数(::＝(无符号整数(|(十进分数(| (无符号整数((十进分数( (十进分数(::=.(无符号整数( (无符号整数(::=(十进数字(| (十进数字((无符号整数( (十进数字(::=0|1|2|3|4|5|6|7|8|9 23.14 例4. G=(V,S,identifier,→) N＝{identifier,remaining,digit,letter} S＝{a,b,c,……,z,0,1,2,……，9} V=N∪S 1．(identifier(::＝(letter(| (letter((remain