离散数学课件_第十章语_言和自动机.doc

第10章 语言和有限自动机Language and Finite－State Machine §10.1 语言Languages 由符号以一定规则组成单词word， 由单词以一定规则（语法）组成句子sentences。 以一定规则给句子的含义作出解释叫语义。 语言 S={s1,…,sn}为有限字母表。 S*为S上的有限长字符串集合。 S*的子集L称为S上的一个语言 例如: L1={0,1}* L2={(01)*} L3={0n1m:n,m0} L4={0n1n:n0} L5={xx:x(L1} L6={xxR:x(L1} L7={x(L1:x=xR} Grammars文法 G＝（V，S，v0， (）短语结构文法phrase structure grammar V是有限符号集， S(V，S终止符号集 N＝V－S，非终止符号集。 v0∈N，初始符号， →是V*上的有限产生关系product relation。 w，w’∈V*, w→w’是产生规则， w叫左边，w’叫右边。  例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． G=(V,S,v0,→), V＝{v0,w,a,b,c},S={a,b,c}, v0→aw. 2. w→bbw. 3. w→c. G能派生的语句是？ G派生的语言L(G)={ ab2nc|n∈N}＝a(bb)*c. 例3． 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 简记为 G能接受的语句是？ L(G)={ ancbn | n≥0} 形式文法的分类 3型文法type 3：正则文法。RG A→(或A→B(，A，B∈N，((S* 即：左边只含单个非终结字符，右边最右端可以有一个非终结符号。左线性文法。 A→(或A→(B，A，B∈N，((S*左边只含单个非终结字符，右边最右端可以有一个非终结符号。右线性文法。 左线性文法，右线性文法都叫正则文法 有限语言都是正则语言 任何一个左线性文法产生的语言都可以用一个右线性文法来生成。 证明： A→(，A→B(，A→(B同时有这三类产规则的文法叫线性文法。 G={S,A,0,1},{S,A}{S(0A，A(S1，A(1},S L(G)={0n1n:n0} L(G)不是正则语言。 2型文法type 2：CFG A→α，A∈N，左边只含单个非终结字符。 上下文无关文法。 上下文无关文法产生的语言叫上下文无关语言CFL 1型文法type 1：CSG 每条规则左边的长度小于等于右边的长度。 lwr→lw’r,上下文有关文法。 上下文相关文法产生的语言叫上下文相关语言CSL 0型文法type 0：r.e.G 规则无限制.无限制文法。递归可枚举文法 递归可枚举文法产生的语言叫递归可枚举语言r.e. 求下列语言对应的文法 L(G)＝{anbn|n≥3} L(G)={xnym|n,m≥2} L5={xx: {0,1}*} L6={xxR: {0,1}*} L7={x({0,1}*:x=xR} 语言的运算 交集 并集 补集 连接 Kleene star Reverse 带入 封闭性 RL CFL CSL Rec r.e. 交集 Y N Y Y Y 并集 Y Y Y Y Y 补集 Y N Y Y N 连接 Y Y Y Y Y Kleene star Y Y Y Y Y Reverse Y Y Y Y Y 带入 Y Y Y N Y 形式语言对应的问题 Acceptance(membership)： 判断一个字符串是否能由该文法生成 Emptiness： 判断一个文法对应的语言是否为空 Equality： 判断两个文法对应的语言是否一样 Universali