迈希尔－尼罗德定理
在法汉-汉法词典中发现10个解释错误，并通过审核，将获赠《法语助手》授权一个
添加笔记：
<div id="correct" title="在法汉-汉法词典中发现10个解释错误，并通过审核，将获赠《法语助手》授权一个">有奖纠错
用途和结论
Myhill–Nerode 定理的一个结论是语言 L 是正则的(就是说可被接受)， RL 的等价类的数目是有限的。
直接是如果一个语言定义等价类的无限集合，它就不是正则的。这个推论经常被用来证明一个语言不是正则的。
例如，由可以被 3 整除的二进制数组成的语言是正则的。有三个等价类 3 - 被 3 除的时候余数是 0, 1 和 2 的数。接受这个语言的极小自动机有对应于等价类的三个状态。
A. Nerode, "Linear automaton transformations", Proceedings of the AMS, 9 (1958) pp 541-544.
John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 3.)
Tom Henzinger,
关注我们的微信
下载手机客户端
赞助商链接
在法语课堂快速找到适合自己的法语学习课程/course
欧洲最具活力的中文社区.最大的关于法国的中文网络平台
法语爱好者的家园 留学与考试的助手 提供各种法语相关的信息与服务【图文】形式语言第五章_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
形式语言第五章
&&形式语言与自动机理论-蒋宗礼,ppt讲义
大小：1.92MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢计算机科学与技术学院
计算机科学与技术学院
题目：Neural Information Retrieval
时间：日10:00
地点：东区网络中心会议室
题目：跨域大数据的价值、隐私和价格
时间：日16:00
地点：西区电三楼632学术报告厅
题目：用可编程硬件加速数据中心基础架构
时间：日14:00
地点：西区电三楼632学术报告厅
您现在的位置：>>
德国慕尼黑理工大学Christian Urban博士来访并作学术报告
　　4月15日，应中科大—耶鲁高可信软件联合研究中心邀请，德国慕尼黑理工大学的Christian Urban博士来我院进行访问，并作题为 “Verifying A Regular Expression Matcher and Formal Language Theory”的学术报告。计算机学院冯新宇教授主持报告会，计算机学院部分师生参加了报告会。
　　Christian Urban博士2000年毕业于英国剑桥大学并获博士学位，随后在剑桥大学、普林斯顿大学和慕尼黑理工大学等多所国际著名院校和研究机构从事程序语言理论、定理证明器以及编译器相关的研究工作。Christian Urban博士是著名定理证明器Isabelle的核心开发者之一，近年来主要关注自动定理证明、程序语言等理论领域，已在国际顶级学术会议和期刊上发表多篇论文。
　　Christian Urban博士为师生们介绍了机器可检查的证明在计算机理论研究和程序验证中的重要性，讲解了Isabelle中相关算法的实现，以及如何使用逻辑语言来形式化地严格证明算法的正确性。Christian Urban博士还重点介绍了与国内高校合作所取得的最新成果——如何应用Isabelle来证明自动机理论领域中的Myhill-Nerode 定理。这一成果将在知名国际会议Interactive Theorem Proving 2011上发表。
　　4月25日，Christian Urban博士还访问了中科大—耶鲁高可信软件联合研究中心的苏州实验室，与师生们进行了更深入的交流。他分析了Isabelle与其它定理证明器的不同之处，并热情回答了同学们的提问。他还兴致勃勃地向师生们展示了Isabelle工具的使用和特点。最后，Christian Urban博士还表示了未来进行深入合作的意向。
Christian Urban博士与师生们座谈&Christian Urban博士正在展示Isabelle定理证明器的使用
中国科学技术大学计算机科学与技术学院 All Rights Reserved.
安徽省合肥市黄山路中国科学技术大学西区电三楼
通信地址：安徽省合肥市４号信箱 计算机科学与技术学院 邮政编码：230027形式语言与自动机理论电子教案_形式语言与自动机理论_ppt_大学课件预览_高等教育资讯网
形式语言与自动机理论：形式语言与自动机理论电子教案
分类： 格式： 日期：日
1形式语言与自动机理论Formal Languages and AutomataTheory蒋宗礼 2课程目的和基本要求课程性质C 技术基础基础知识要求C 数学分析（或者高等数学），离散数学主要特点C 抽象和形式化C 理论证明和构造性C 基本模型的建立与性质 3课程目的和基本要求本专业人员 4种基本的专业能力C 计算思维能力C 算法的设计与分析能力C 程序设计和实现能力C 计算机软硬件系统的认知、分析、设计与应用能力计算思维能力C 逻辑思维能力和抽象思维能力C 构造模型对问题进行形式化描述C 理解和处理形式模型 4课程目的和基本要求知识C 掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。能力C 培养学生的形式化描述和抽象思维能力。C 使学生了解和初步掌握,问题、形式化描述、自动化（计算机化）,这一最典型的计算机问题求解思路。 5主要内容语言的 文法 描述 。RLC RG,FA,RE,RL的性质 。CFLC CFG(CNF,GNF),PDA,CFL的性质 。TMC 基本 TM,构造技术,TM的修改 。CSLC CSG,LBA。 6教材及主要参考书目1.蒋宗礼,姜守旭,形式语言与自动机理论,北京：清华大学出版社,2003年2,John E Hopcroft,Rajeev Motwani,Jeffrey DUllman,Introduction to Automata Theory,Languages,and Computation (2nd Edition).Addison-Wesley Publishing Company,20013,John E Hopcroft,Jeffrey D Ullman,Introductionto Automata Theory,Languages,andComputation,Addison-Wesley PublishingCompany,1979 7第 1章 绪论1.1 集合的基础知识1.1.1 集合及其表示C 集合：一定范围内的,确定的,并且彼此可以区分的对象汇集在一起形成的整体叫做 集合 (set)，简称为集 (set)。C 元素：集合的成员为该集合的 元素 (element)。C 集合描述形式 。C 基数 。C 集合的分类 。 81.1.2 集合之间的关系子集如果集合 A中的每个元素都是集合 B的元素,则称集合 A是集合 B的 子集 (subset),集合 B是集合 A的 包集 (container)。 记作 A?B。 也可记作 B?A。 A?B读作集合 A包含在集合 B中；B?A读作集合 B包含集合 A。如果 A?B,且?x∈ B,但 x?A,则称 A是 B的真子集 (proper subset),记作 A?B 91.1.2 集合之间的关系集合相等C 如果集合 A,B含有的元素完全相同,则称集合 A与集合 B相等 (equivalence),记作 A=B。对任意集合 A,B,C：⑴ A=B iff A?B且 B?A。⑵ 如果 A?B,则 |A|≤|B|。⑶ 如果 A?B,则 |A|≤|B|。⑷ 如果 A是有穷集,且 A?B,则 |B|&|A|。 101.1.2 集合之间的关系⑸ 如果 A?B,则对?x∈ A,有 x∈ B。⑹ 如果 A?B,则对? x∈ A,有 x∈ B并且x∈ B,但 x?A。⑺ 如果 A?B且 B?C,则 A?C。⑻ 如果 A?B且 B?C,或者 A?B且 B?C,或者A?B且 B?C,则 A?C。⑼ 如果 A=B,则 |A|=|B|。 111.1.3 集合的运算并 (union)A与 B的 并 (union)是一个集合,该集合中的元素要么是 A的元素,要么是 B的元素,记作 A∪ B。A∪ B={a|a∈ A或者 a∈ B}A1∪ A2∪ … ∪ An={a|?i,1? i? n,使得 a∈ Ai}A1∪ A2∪ … ∪ An ∪ … ={a|?i,i∈ N,使得 a∈ Ai}1iiA},|{ AaSAaASA 12交 (intersection)集合 A和 B中都有的所有元素放在一起构成的集合为 A与 B的 交,记作 A∩ B。A∩ B={a|a∈ A且 a∈ B},∩,为交运算符,A∩ B读作 A交 B。如果 A∩ B=Φ,则称 A与 B不相交 。⑴ A∩B=B∩A。⑵ (A∩B)∩C=A∩(B∩C)。⑶ A∩A=A。 13交 (intersection)⑷ A∩B=A iff A?B。⑸ Φ∩A=Φ。⑹ |A∩B|≤min{|A|,|B|}。⑺ A∩(B∪ C)=(A∩B)∪ (A∩C)。⑻ A∪ (B∩C)=(A∪ B)∩(A∪ C)。⑼ A∩(A∪ B)=A。⑽ A∪ (A∩B)=A。 14差 (difference)属于 A,但不属于 B的所有元素组成的集合叫做 A与 B的 差,记作 A-B。A-B={a|a∈ A且 a?B},-”为减 (差 )运算符,A-B读作 A减 B。⑴ A-A=Φ。⑵ A-Φ=A。⑶ A-B ≠ B-A。⑷ A-B=A iff A∩B=Φ。⑸ A∩(B-C)=(A∩B)-(A∩C)。⑹ |A-B|≤|A|。 15对称差 (symmetric difference)属于 A但不属于 B,属于 B但不属于 A的所有元素组成的集合叫 A与 B的 对称差,记作 AB 。AB={a|a∈A 且 a?B或者 a?A且 a∈B},,为对称差运算符 。 AB 读作 A对称减 B。AB=(A∪B) -(A∩B)=(A -B)∪(B -A)。 16笛卡儿积 (Cartesian product)A与 B的 笛卡儿积 (Cartesian product)是一个集合,该集合是由所有这样的有序对 (a,b)组成的：其中 a∈ A,b∈ B,记作 A&#215;B。A&#215;B={(a,b)|a∈ A& b∈ B }。,&#215;”为笛卡儿乘运算符 。 A&#215;B读作 A叉乘 B。⑴ A&#215;B≠ B&#215;A。⑵ (A&#215;B)&#215;C≠ A&#215;(B&#215;C)。⑶ A&#215;A≠ A。⑷ A&#215;Φ =Φ。 17笛卡儿积 (Cartesian product)⑸ A&#215;(B∪ C)=(A&#215;B)∪ (A&#215;C)。⑹ (B∪ C)&#215;A=(B&#215;A)∪ (A&#215;C)。⑺ A&#215;(B∩ C)=(A&#215;B)∩ (A&#215;C)。⑻ (B∩ C)&#215;A=(B&#215;A)∩ (C&#215;A)。⑼ A&#215;(B-C)=(A&#215;B)-(A&#215;C)。⑽ (B-C)&#215;A=(B&#215;A)-(C&#215;A)。⑾ 当 A,B为有穷集时,|A&#215;B|=|A|*|B|。 18幂集 (power set)A幂集 (power set)是一个集合，该集合是由 A的所有子集组成的，记作 2A。2A={B|B?A}。2A读作 A的幂集。 19幂集 (power set)⑴ Φ∈ 2A。⑵ Φ?2A。⑶ Φ?2A。⑷ 2Φ={Φ}。⑸ A∈ 2A。⑹ 如果 A是有穷集,则 |2A|=2|A|。⑺ 2A∩B=2A∩2B。⑻ 如果 A?B，则 2A?2B。 20补集 (complementary set)A是论域 U上的一个集合,A补集 是由 U中的、不在 A中的所有元素组成的集合，记作AUAUU 21补集 (complementary set)AA? BAUBAAB &BABABABAAB?UAA如果 A?B，则 。。。。。。 221.2 关系二元关系递归定义与归纳证明关系的闭包 231.2.1 二元关系 (binary relation)二元关系C 任意的 R?A&#215;B,R是 A到 B的 二元关系。C (a,b) ∈ R，也可表示为,aRb。C A称为 定义域 (domain),B称为 值域 (range)。C 当 A=B时，则称 R是 A上的二元关系。二元关系的性质C 自反 (reflexive)性、反自反 (irreflexive)性、对称(symmetric)性、反对称 (asymmetric)性、传递(transitive)性。 241.2.1 二元关系 (binary relation)三歧性C自反性、对称性、传递性。等价关系 (equivalence relation)C具有三歧性的二元关系称为 等价关系。 251.2.1 二元关系 (binary relation)等价类 (equivalence class)S的满足如下要求的划分,S1,S2,S3,…,Sn… 称为 S关于 R的等价划分,Si称为等价类。⑴ S= S1∪ S2∪ S3∪ … ∪ Sn∪ … ；⑵ 如果 i≠j,则 Si∩Sj=Φ；⑶ 对任意的 i,Si中的任意两个元素 a,b,aRb恒成立；⑷ 对任意的 i,j,i≠j,Si中的任意元素 a和 Sj中的任意元素 b,aRb恒不成立 261.2.1 二元关系 (binary relation)指数 (index)C 把 R将 S分成的等价类的个数称为是 R在 S上的指数 。如果 R将 S分成有穷多个等价类，则称 R具有有穷指数；如果 R将 S分成无穷多个等价类，则称 R具有无穷指数。C 给定集合 S上的一个等价关系 R,R就确定了 S的一个等价分类，当给定另一个不同的等价关系时，它会确定 S的一个新的等价分类。 271.2.1 二元关系 (binary relation)关系的合成 (composition)设 R1?A&#215; B是 A到 B的关系,R2?B&#215; C是 B到C的关系,R1与 R2的 合成 R1R2是 A到 C的关系：R1R2={(a,c)|?(a,b) ∈ R1且 (b,c) ∈ R2 。 281.2.1 二元关系 (binary relation)⑴ R1R2≠R2R1。⑵ (R1R2)R3=R1(R2R3)。 (结合率 )⑶ (R1∪ R2)R3=R1R3∪ R2R3。 (右分配率 )⑷ R3(R1∪ R2)=R3R1∪ R3R2。 (左分配率 )⑸ (R1∩R2)R3?R1R3∩R2R3。⑹ R3(R1∩R2)?R3R1∩R3R2。 291.2.1 二元关系 (binary relation)1,关系这一个概念用来反映对象 ――集合元素之间的联系和性质2,二元关系则是反映两个元素之间的关系,包括某个元素的某种属性 。3,对二元关系的性质,要强调全称量词是对什么样的范围而言的 。 301.2.2 等价关系与等价类 （略）1.2.3 关系的合成 （略） 311.2.4 递归定义与归纳证明递归定义 (recursive definition)C 又称为 归纳定义 (inductive definition)，它来定义一个集合。C 集合的递归定义由三部分组成：基础 (basis)：用来定义该集合的最基本的元素。归纳 (induction)：指出用集合中的元素来构造集合的新元素的规则。极小性限定：指出一个对象是所定义集合中的元素的充要条件是它可以通过有限次的使用基础和归纳条款中所给的规定构造出来。 321.2.4 递归定义与归纳证明归纳证明C 与递归定义相对应。C 归纳证明方法包括三大步：基础 (basis)：证明最基本元素具有相应性质。归纳 (induction)：证明如果某些元素具有相应性质，则根据这些元素用所规定的方法得到的新元素也具有相应的性质。根据归纳法原理，所有的元素具有相应的性质。 331.2.4 递归定义与归纳证明定义 1-17设 R是 S上的关系,我们递归地定义 Rn的幂：⑴ R0={(a,a)|a∈ S}。⑵ Ri=Ri-1R (i=1,2,3,4,5,…) 。 341.2.4 递归定义与归纳证明例 1-17 著名的斐波那契 (Fibonacci)数的定义⑴ 基础,0是第一个斐波那契数,1第二个斐波那契数；⑵ 归纳：如果 n是第 i个斐波那契数,m是第 i+1个斐波那契数,则 n+m是第 i+2个斐波那契数,这里 i为大于等于 1的正整数 。⑶ 只有满足 (1)和 (2)的数才是斐波那契数0,1,1,2,3,5,8,13,21,34，55,… 351.2.4 递归定义与归纳证明例 1-18算术表达式⑴ 基础：常数是算术表达式,变量是算术表达式；⑵ 归纳：如果 E1,E2是表达式,则 +E1,-E1、E1+E2,E1-E2,E1*E2,E1/E2,E1**E2、Fun(E1)是算术表达式 。 其中 Fun为函数名 。⑶ 只有满足 (1)和 (2)的才是算术表达式。 361.2.4 递归定义与归纳证明例 1-19对有穷集合 A,证明 |2A|=2|A|。证明：设 A为一个有穷集合,施归纳于 |A|：⑴ 基础：当 |A|=0时,|2A|=|{Φ}|=1。⑵ 归纳：假设 |A|=n时结论成立，这里 n ≥0，往证当 |A|=n+1时结论成立2A=2B∪ {C∪ {a}|C∈ 2B}2B∩{C∪ {a}|C∈ 2B}=Φ 371.2.4 递归定义与归纳证明|2A|=|2B∪ {C∪ {a}|C∈ 2B}|=|2B|+|{C∪ {a}|C∈ 2B}|=|2B|+|2B|=2*|2B|=2*2|B|=2|B|+1=2|A|⑶ 由归纳法原理,结论对任意有穷集合成立 。 381.2.4 递归定义与归纳证明例 1-20 表达式的前缀形式是指将运算符写在前面，后跟相应的运算对象。如,+E1的前缀形式为 +E1,E1+E2的前缀形式为 +E1E2,E1*E2的前缀形式为 *E1E2,E1**E2的前缀形式为 ** E1,Fun(E1) 的前缀形式为 FunE1 。证明例 1-18所定义的表达式可以用这里定义的前缀形式表示。 391.2.4 递归定义与归纳证明递归定义给出的概念有利于归纳证明。在计算机科学与技术学科中，有许多问题可以用递归定义描述或者用归纳方法进行证明，而且在许多时候，这样做会带来许多方便。主要是掌握 递归定义与归纳证明 的叙述格式。 401.2.5 关系的闭包闭包 (closure)C 设 P是关于关系的性质的集合，关系 R的 P闭包(closure)是包含 R并且具有 P中所有性质的最小关系 。正闭包 (positive closure)(1)R?R+。(2)如果 (a,b),(b,c)∈ R+ 则 (a,c)∈ R+。(3)除 (1),(2)外,R+不再含有其他任何元素 。 411.2.5 关系的闭包传递闭包 (transitive closure)C 具有传递性的闭包 。C R+具有传递性 。可以证明,对任意二元关系 R，R+= R∪ R2∪ R3∪ R4∪ …而且当 S为有穷集时：R+= R∪ R2∪ R3∪ … ∪ R|S| 421.2.5 关系的闭包克林闭包 (Kleene closure) R*(1) R0? R*,R? R*。(2) 如果 (a,b),(b,c)∈R * 则 (a,c)∈R *。(3) 除 (1),(2)外,R*不再含有其他任何元素。自反传递闭包 (reflexive and transitiveclosure)R*具有自反性、传递性 。 431.2.5 关系的闭包可以证明,对任意二元关系 R，R*= R0∪ R+R* =R0∪ R∪ R2∪ R3∪ R4∪ …而且当 S为有穷集时：R*= R0∪ R∪ R2∪ R3∪ … ∪ R|S| 441.2.5 关系的闭包R1,R2是 S上的两个二元关系(1) Φ+=Φ。(2) (R1+)+= R1+。(3) (R1*)*= R1*。(4) R1+∪ R2+?(R1∪ R2)+。(5) R1*∪ R2*?(R1∪ R2)*。 451.3 图数学家欧拉 (L.Euler)解决著名的哥尼斯堡七桥。直观地讲，图是由一些点和一些连接两点的边组成。含无方向的边的图为无向图，含带有方向的边的图为有向图。 461.3.1 无向图无向图 (undirected graph)C 设 V是一个非空的有穷集合,E?V&#215;V,G=(V，E)称为 无向图 (undirected graph)。其中 V中的元素称为 顶点 (vertex或 node),V称为顶点集，E中的元素称为 无向边 (undirected edge),E为无向边集。图表示C V中称为顶点 v的元素用标记为 v的小圈表示,E中的元素 (v1,v2)用标记为 v1,v2的顶点之间的连线表示。 471.3.1 无向图路 (path)C 如果对于 0≤i≤k-1,k≥1，均有 (vi,vi+1)∈ E，则称 v0,v1,…,vk是 G=(V,E)的一条长为 k的路。回路或圈 (cycle)C 当路 v0,v1,…,vk中 v0=vk时,v0,v1,…,vk叫做一个 回路或圈 (cycle)。 481.3.1 无向图顶点的度数C 对于 v∈ V,|{v|(v,w)∈ E}|称为无向图 G=(V，E)的顶点 v的度数,记作 deg(v)。C 对于任何一个图，图中所有顶点的度数之和为图中边的 2倍。VvEv ||*2)d e g ( 49deg(v1)=3deg(v2)=3deg(v3)=4deg(v4)=3deg(v5)=3deg(v1)+deg(v2)+deg(v3)+deg(v4)+deg(v5)=16 501.3.1 无向图连通图C 如果对于?v,w∈ V,v≠w,v与 w之间至少有一条路存在，则称 G=(V,E)是 连通图 。C 图 G是连通的充要条件是 G中存在一条包含图的所有顶点的路。 511.3.2 有向图有向图 (directed graph)C G=(V,E)。C V,顶点 (vertex或 node)集。C (v1,v2)∈ E,顶点 v1到顶点 v2的 有向边(directed edge)，或 弧 (arc),v1称为 前导(predecessor),v2称为 后继 (successor)。有向路 (directed path)C 如果对于 0? i? k-1,k? 1，均有 (vi,vi+1)∈ E，则称 v0,v1,…,vk是 G的一条长为 k的 有向路。 521.3.2 有向图有向回路或有向圈 (directed cycle)C 对于 0? i? k-1,k? 1，均有 (vi,vi+1)∈ E,且v0=vk，则称 v0,v1,…,vk是 G的一条长为 k的有向路为 一个 有向回路。C 有向回路又叫有向圈。有向图的图表示C 图 G的图表示是满足下列条件的,图,,其中 V中称为顶点 v的元素用标记为 v的小圈表示,E中的元素 (v1,v2)用从标记为 v1的顶点到标记为 v2的顶点的弧表示。 531.3.2 有向图顶点的度数C 入度 (数 ),ideg(v)=|{v|(w,v)∈ E}|。C 出度 (数 ),odeg(v)= |{v|(v,w)∈ E}|。对于任何一个有向图，图中所有顶点的入度之和与图中所有顶点的出度之和正好是图中边的个数VvVvEvovi ||)d e g ()d e g ( 54两个不同的有向图 551.3.3 树满足如下条件的有向图 G=(V,E)称为一棵(有序、有向 )树 (tree)：C 根 (root) v,没有前导，且 v到树中其他顶点均有一条有向路。C 每个非根顶点有且仅有一个前导。C 每个顶点的后继按其拓扑关系从左到右排序。 561.3.3 树树的基本概念(1) 顶点也可以成为结点。(2) 结点的前导为该结点的 父亲 (父结点 father)。(3) 结点的后继为它的 儿子 (son)。(4) 如果树中有一条从结点 v1到结点 v2的路，则称v1是 v2的 祖先 (ancestor),v2是 v1的 后代 (descendant)。(5) 无儿子的顶点叫做 叶子 (leaf)。(6) 非叶结点叫做 中间结点 (interior)。 571.3.3 树树的层C 根处在树的第 1层 (level)。C 如果结点 v处在第 i层 (i? 1)，则 v的儿子处在第i+1层 。C 树的最大层号叫做该树的高度 (height)。 581.3.3 树二元树C 如果对于?v∈ V,v最多只有 2个儿子，则称G=(V,E)为 二元树 (binary tree)。C 对一棵二元树，它的第 n层最多有 2n-1个结点。一棵 n层二元树最多有个 2n-1叶子。 591.4 语言1.4.1 什么是语言例如：,学大一生是个我,；,我是一个大学生,。语言是一定的群体用来进行交流的工具。必须有着一系列的生成规则、理解 (语义 )规则 。 601.4.1 什么是语言 611.4.1 什么是语言斯大林：从强调语言的作用出发，把语言定义为,为广大的人群所理解的字和组合这些字的方法,。语言学家韦波斯特 (Webster),为相当大的团体的人所懂得并使用的字和组合这些字的方法的统一体。要想对语言的性质进行研究，用这些定义来建立语言的数学模型是不够精确的。必须有更形式化的定义。 621.4.2 形式语言与自动机理论的产生与作用语言学家乔姆斯基，毕业于宾西法尼亚大学，最初从产生语言的角度研究语言。1956年，他将语言 L定义为一个字母表 ∑ 中的字母组成的一些串的集合,L?∑ *。字母表上按照一定的规则定义一个文法(grammar)，该文法所能产生的所有句子组成的集合就是该文法产生的语言。1959年，乔姆斯基根据产生语言文法的特性，将语言划分成 3大类。 631.4.2 形式语言与自动机理论的产生与作用1951年到 1956年，克林 (Kleene) 在研究神经细胞中，建立了识别语言的系统 ――有穷状态自动机。1959年，乔姆斯基发现文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性，这一成果被认为是将形式语言置于了数学的光芒之下，使得形式语言真正诞生了。 641.4.2 形式语言与自动机理论的产生与作用20世纪 50年代，巴科斯范式 (Backus NourForm 或 Backus Normal Form,BNF)实现了对高级语言 ALGOL-60的成功描述。这一成功，使得形式语言在 20世纪 60年代得到了大力的发展。尤其是上下文无关文法被作为计算机程序设计语言的文法的最佳近似描述得到了较为深入的研究。相应的理论用于其他方面。 651.4.2 形式语言与自动机理论的产生与作用形式语言与自动机理论在计算机科学与技术学科的人才的计算思维的培养中占有极其重要的地位。计算学科的主题：,什么能被有效地自动化,。 661.4.2 形式语言与自动机理论的产生与作用计算机科学与技术学科人才专业能力构成C,计算思维能力,――抽象思维能力、逻辑思维能力。C 算法设计与分析能力 。C 程序设计与实现能力 。C 计算机系统的认知、分析、设计和应用能力。 671.4.2 形式语言与自动机理论的产生与作用 681.4.2 形式语言与自动机理论的产生与作用考虑的对象的不同，所需要的思维方式和能力就不同，通过这一系统的教育，在不断升华的过程中，逐渐地培养出了学生的抽象思维能力和对逻辑思维方法的掌握。创新意识的建立和创新能力的培养也在这个教育过程中循序渐进地进行着。内容用于后续课程和今后的研究工作。是进行思维训练的最佳知识载体。是一个优秀的计算机科学工作者必修的一门课程。 691.4.3 基本概念对语言研究的三个方面C 表示 (representation)―― 无穷语言的表示。C 有穷描述 (finite description) ――研究的语言要么是有穷的，要么是可数无穷的，这里主要研究可数无穷语言的有穷描述。C 结构 (structure)――语言的结构特征。 701.4.3 基本概念字母表 (alphabet)C 字母表 是一个非空有穷集合，字母表中的元素称为该字母表的一个 字母 (letter)。又叫做 符号(symbol)、或者 字符 (character)。C 非空性。C 有穷性。例如：{a,b,c,d}{ a,b,c,…,z}{0,1} 711.4.3 基本概念字符的两个特性C 整体性 (monolith)，也叫不可分性。C 可辨认性 (distinguishable)，也叫可区分性。例（续）{a,a′,b,b′}{aa,ab,bb}{∞,∧,∨,≥,≤} 721.4.3 基本概念字母表的乘积 (product)∑1∑2={ab|a∈ ∑1,b∈ ∑2}例如：{0,1}{0,1}={00,01,10,00}{0,1}{a,b,c,d}={0a,0b,0c,0d,1a,1b，1c,1d}{a,b,c,d}{0,1}={a0,a1,b0,b1,c0,c1，d0,d1}{aa,ab,bb}{0,1}={ aa0,aa1,ab0,ab1,bb0，bb1} 731.4.3 基本概念字母表 ∑的 n次 幂∑0={ε}∑n=∑n-1∑ε是由 ∑中的 0个字符组成的。∑的 正闭包∑+=∑∪ ∑2∪ ∑3∪ ∑4∪ …∑的 克林闭包∑*=∑0∪ ∑+=∑0∪ ∑∪ ∑2∪ ∑3∪ … 741.4.3 基本概念例如：{0,1}+={0,1,00,01,11,000,001,010,011，100,…}{0,1}*={ε,0,1,00,01,11,000,001,010，011,100,…}{a,b,c,d}+={a,b,c,d,aa,ab,ac,ad,ba，bb,bc,bd,…,aaa,aab,aac,aad,aba,abb，abc,…}{a,b,c,d}*={ε,a,b,c,d,aa,ab,ac,ad，ba,bb,bc,bd,…,aaa,aab,aac,aad,aba，abb,abc,…} 751.4.3 基本概念结论：∑*={x|x是 ∑中的若干个,包括 0个字符,连接而成的一个字符串 }。∑+={x|x是 ∑中的至少一个字符连接而成的字符串 }。 761.4.3 基本概念句子 (sentence)∑是一个字母表,?x∈ ∑*,x叫做 ∑上的一个 句子。句子相等。两个句子被称为相等的，如果它们对应位置上的字符都对应相等。别称字 (word),(字符、符号 )行 (line),(字符、符号 )串(string)。 771.4.3 基本概念出现 (apperance)C x,y∈ ∑*,a∈ ∑，句子 xay中的 a叫做 a在该句子中的一个 出现。C 当 x=ε时,a的这个出现为字符串 xay的首字符C 如果 a的这个出现是字符串 xay的第 n个字符，则 y的首字符的这个出现是字符串 xay的第 n+1个字符。C 当 y=ε时,a的这个出现是字符串 xay的尾字符C 例,abaabb。 781.4.3 基本概念句子的长度 (length)C?x∈ ∑*，句子 x中字符出现的总个数叫做该 句子的长度,记作 |x|。C 长度为 0的字符串叫 空句子,记作 ε。例如：|abaabb|=6|bbaa|=4|ε|=0|bbabaabbbaa|=11 791.4.3 基本概念注意事项C ε是一个句子。C {ε}≠Φ。这是因为 {ε}不是一个空集，它是含有一个空句子 ε的集合。 |{ε}|=1，而 |Φ|=0。 801.4.3 基本概念并置 (concatenation)C x,y∈ ∑*,x,y的 并置 是由串 x直接相接串 y所组成的。记作 xy。并置又叫做 连结。串 x的 n次 幂x0=εxn=xn-1x 811.4.3 基本概念例 如：C 对 x=001,y=1101x0=y0=εx4=y4=1101C 对 x=0101,y=110110x2=y2=x4=0101y4= 821.4.3 基本概念∑*上的并置运算性质⑴ 结合律,(xy)z=x(yz)。⑵ 左消去律：如果 xy=xz,则 y=z。⑶ 右消去律：如果 yx=zx,则 y=z。⑷ 惟一分解性：存在惟一确定的 a1,a2,…,an∈ ∑,使得 x= a1a2… an。⑸ 单位元素,εx=xε=x。 831.4.3 基本概念前缀与后缀设 x,y,z,w,v∈ ∑*，且 x=yz,w=yv(1) y是 x的前缀 (prefix)。(2)如果 z≠ε,则 y是 x的真前缀 (proper prefix)。(3) z是 x的后缀 (suffix)；(4) 如果 y≠ε,则 z是 x的真后缀 (proper suffix)。(5) y是 x和 w的公共前缀 (common Prefix)。 841.4.3 基本概念公共 前缀与后缀(6)如果 x和 w的任何公共前缀都是 y的前缀，则 y是 x和 w的最大公共前缀。(7) 如果 x=zy,w=vy，则 y是 x和 w的公共后缀 (commonsuffix )。(8)如果 x和 w的任何公共后缀都是 y的后缀，则 y是 x和 w的最大公共后缀。 851.4.3 基本概念例字母表 ∑={a,b}上的句子 abaabb的前缀,后缀,真前缀和真后缀如下：前缀,ε,a,ab,aba,abaa,abaab,abaabb真前缀,ε,a,ab,aba,abaa,abaab后缀,ε,b,bb,abb,aabb,baabb,abaabb真后缀,ε,b,bb,abb,aabb,baabb 861.4.3 基本概念结论⑴ x的任意前缀 y有惟一的一个后缀 z与之对应,使得x=yz；反之亦然 。⑵ x的任意真前缀 y有惟一的一个真后缀 z与之对应,使得 x=yz；反之亦然 。⑶ |{w|w是 x的后缀 }|=|{w|w是 x的前缀 }|。⑷ |{w|w是 x的真后缀 }|=|{w|w是 x的真前缀 }|。⑸ {w|w是 x的前缀 }={w|w是 x的真前缀 }∪ {x}，|{w|w是 x的前缀 }|=|{w|w是 x的真前缀 }|+1。 871.4.3 基本概念结论⑹ {w|w是 x的后缀 }={w|w是 x的真后缀 }∪ {x}，|{w|w是 x的后缀 }|=|{w|w是 x的真后缀 }|+1。⑺ 对于任意字符串 w,w是自身的前缀,但不是自身的真前缀； w是自身的后缀,但不是自身的真后缀 。⑻ 对于任意字符串 w,ε是 w的前缀，且是 w的真前缀； ε是 w的后缀，且是 w的真后缀 881.4.3 基本概念约定⑴ 用小写字母表中较为靠前的字母 a,b，c,… 表示字母表中的字母 。⑵ 用小写字母表中较为靠后的字母 x,y，z,… 表示字母表上的句子 。⑶ 用 xT表示 x的倒序。例如，如果 x=abc，则xT=cba。 891.4.3 基本概念子串 (substring)C w,x,y,z∈ ∑*，且 w=xyz，则称 y是 w的 子串。公共子串 (common substring)C t,u,v,w,x,y,z∈ ∑*，且 t=uyv,w=xyz，则称 y是 t和 w的 公共子串 (common substring)。如果 y1,y2,……,yn是 t和 w的公共子串，且max{|y1|,|y2|,…,|yn|}=|yj|，则称 yj是 t和 w的最大公共子串。C 两个串的最大公共子串并不一定是惟一的。 901.4.3 基本概念语言 (language)L?∑*,L称为字母表 ∑上的一个 语言(language),?x∈ L,x叫做 L的一个句子。例,{0,1}上的不同语言{00,11},{0,1}{0,1,00,11},{0,1,00,11,01,10}{00,11}*,{01,10}*,{00,01,10,11}*，{0}{0,1}*{1},{0,1}*{111}{0,1}* 911.4.3 基本概念语言的 乘积 (product)L1?∑1*,L2?∑2*,语言 L1与 L2的 乘积 是一个语言,该语言定义为：L1L2={xy| x∈ L1,y∈ L2}是字母表 ∑1∪ ∑2上的语言。 921.4.3 基本概念例⑴ L1={0,1}。⑵ L2={00,01,10,11}。⑶ L3={0,1,00,01,10,11,000,… }=∑+。⑷ L4={ε,0,1,00,01,10,11,000,… }=∑*。⑸ L5={0n|n≥1}。⑹ L6={0n1n|n≥1}。⑺ L7={1n|n≥1}。⑻ L8={0n1m|n,m≥1}。⑼ L9={0n1n0n|n≥1}。⑽ L10={0n1m0k|n,m,k≥1}。⑾ L11={x|x∈ ∑+且 x中 0和 1的个数相同 }。 931.4.3 基本概念上述几个语言的部分特点及相互关系上述所有语言都是 L4的子集 (子语言 )；L1,L2是有穷语言；其他为无穷语言；其中 L1是 ∑上的所有长度为 1的句子组成的语言,L2是 ∑ 上的所有长度为 2的句子组成的语言；L3,L4分别是 ∑ 的正闭包和克林闭包；L5L7≠ L6，但 L5L7= L8；同样 L9≠ L10，但是我们有,L6?L5L7,L9?L10。 941.4.3 基本概念L6={0n1n|n? 1}中的句子中的 0和 1的个数是相同的,并且所有的 0在所有的 1的前面,L11={x|x∈∑ +且 x中 0和 1的个数相同 }中的句子中虽然保持着 0的个数和 1的个数相等,但它并没要求所有的 0在所有的 1的前面 。例如,∈ L11,但是 0101? L6，1100?L6。 而对?x∈ L6,有 x∈ L11。 所以,L6?L11。 951.4.3 基本概念L1?L12,L2?L12L5?L12,L6?L12L7?L12,L8?L12L9?L12,L10?L12L1?L10,L2?L10L5?L10,L6?L10L7?L10,L8?L10L9?L10,L10?L12 961.4.3 基本概念例⑴ {x|x=xT,x∈∑ }。⑵ {xxT|x∈∑ +}。⑶ {xxT|x∈∑ *}。⑷ {xwxT|x,w∈∑ +}。⑸ {xxTw|x,w∈∑ +}。 971.4.3 基本概念幂L∈∑ *,L的 n次 幂 是一个语言，该语言定义为⑴ 当 n=0是,Ln={ε }。⑵ 当 n? 1时,Ln= Ln-1L 。正闭包L+=L∪ L2∪ L3∪ L4∪ …克林闭包L*= L0∪ L∪ L2∪ L3∪ L4∪ … 981.5 小结本章简单叙述了一些基础知识，一方面，希望读者通过对本章的阅读，熟悉集合、关系、图、形式语言等相关的一些基本知识点，为以后各章学习作适当的准备。另一方面，也使读者熟悉本书中一些符号的意义。 991.5 小结(1) 集合：集合的表示,集合之间的关系,集合的基本运算 。(2) 关系：主要介绍了二元关系相关的内容 。包括等价关系,等价分类,关系合成,关系闭包 。(3) 递归定义与归纳证明 。 1001.5 小结(4) 图：无向图,有向图,树的基本概念 。(5) 语言与形式语言：自然语言的描述,形式语言和自动机理论的出现,形式语言和自动机理论对计算机科学与技术学科人才能力培养的作用(6) 基本概念：字母表,字母,句子,字母表上的语言,语言的基本运算 101第 2章 文法对任何语言 L，有一个字母表 ∑,使得 L?∑ * 。L的具体组成结构是什么样的？一个给定的字符串是否为一个给定语言的句子?如果不是，它在结构的什么地方出了错？进一步地，这个错误是什么样的错？如何更正？ …… 。这些问题对有穷语言来说，比较容易解决。这些问题对无穷语言来说，不太容易解决。语言的有穷描述。 102第 2章 文法主要内容文法的直观意义与形式定义,推导,文法产生的语言,句子,句型； 乔姆斯基 体系,左线性文法,右线性文法,文法的推导与归约；空语句 。重点文法,推导,归约,模型的等价性证明 。难点形式化的概念，文法的构造 。 1032.1 启示文法的概念最早是由语言学家们在研究自然语言理解中完成形式化。归纳如下句子的描述：⑴ 哈尔滨是美丽的城市 。⑵ 北京是祖国的首都 。⑶ 集合是数学的基础 。⑷ 形式语言是很抽象的 。⑸ 教育走在社会发展的前面 。⑹ 中国进入 WTO。 1042.1 启示6个句子的主体结构&名词短语 &&动词短语 &&句号 &&名词短语 &={哈尔滨,北京,集合,形式语言,教育,中国 }&动词短语 &={是美丽的城市，是祖国的首都，是数学的基础，是很抽象的，走在社会发展的前面，进入 WTO}&句号 &={。 } 1052.1 启示&动词短语 &可以是 &动词 &&形容词短语 & 或者 &动词 &&名词短语 & 。&名词短语 &={北京,哈尔滨,形式语言,中国,教育,集合,WTO,美丽的城市,祖国的首都,数学的基础,社会发展的前面 }。&动词 &={是,走在,进入 }。&形容词短语 &={很抽象的 }。把 &名词短语 &&动词短语 &&句号 &取名为 &句子 &。 1062.1 启示 1072.1 启示表示成 α?β 形式&句子 &?&名词短语 &&动词短语 &&句号 &&动词短语 &?&动词 &&形容词短语 &&动词短语 &?&动词 &&名词短语 &&动词 &?是 1082.1 启示&动词 &?走在&动词 &?进入&形容词短语 &?很抽象的&名词短语 &?北京&名词短语 &?哈尔滨&名词短语 &?形式语言 1092.1 启示&名词短语 &?中国&名词短语 &?教育&名词短语 &?集合&名词短语 &?WTO&名词短语 &?美丽的城市&名词短语 &?祖国的首都&名词短语 &?数学的基础&名词短语 &?社会发展的前面&句号 &?。 1102.1 启示表示一个语言，需要 4种东西⑴形如 &名词短语 &的,符号,它们表示相应语言结构中某个位置上可以出现的一些内容。每个,符号,对应的是一个集合，在该语言的一个具体句子中，句子的这个位置上能且仅能出现相应集合中的某个元素。所以，这种,符号,代表的是一个语法范畴。⑵ &句子 &所有的,规则,,都是为了说明 &句子 &的结构而存在，相当于说，定义的就是 &句子 &。 1112.1 启示⑶ 形如北京的,符号,它们是所定义语言的合法句子中将出现的,符号,。仅仅表示自身，称为终极符号 。⑷所有的,规则,都呈 α?β 的形式在产生语言的句子中被使用，称这些,规则,为产生式。 1122.2 形式定义文法 (grammar)G=(V,T,P,S)C V――为 变量 (variable)的非空有穷集。A∈ V,A叫做一个 语法变量 (syntacticVariable)，简称为变量，也可叫做 非终极符号 (nonterminal)。它表示一个 语法范畴 (syntactic Category)。所以，本文中有时候又称之为语法范畴 。 1132.2 形式定义C T――为 终极符 (terminal)的非空有穷集。a∈ T,a叫做终极符。由于 V中变量表示语法范畴,T中的字符是语言的句子中出现的字符，所以，有 V∩ T=Φ。C S――S∈ V，为文法 G的 开始符号 (startsymbol)。 1142.2 形式定义C P――为 产生式 (production)的非空有穷集合。 P中的元素均具有形式 α?β,被称为产生式，读作,α 定义为 β 。其中 α ∈ (V∪ T)+，且 α 中至少有 V中元素的一个出现。 β ∈ (V∪ T)*。 α 称为产生式 α?β 的 左部,β 称为产生式 α?β的 右部 。产生式又叫做定义式或者语法规则。 1152.2 形式定义例 2-1 以下四元组都是文法。⑴ ({A},{0,1},{A?01,A?0A1,A?1A0},A)。⑵ ({A},{0,1},{A?0,A?0A},A)。⑶ ({A,B},{0,1},{A?01,A?0A1,A?1A0,B?AB，B?0},A)。⑷ ({A,B},{0,1},{A?0,A?1,A?0A,A?1A }，A)。 1162.2 形式定义⑸ ({S,A,B,C,D},{a,b,c,d,#},{S?ABCD，S?abc#,A?aaA,AB?aabbB,BC?bbccC，cC?cccC,CD?ccd#,CD?d#,CD?#d},S)。⑹ ({S},{a,b},{S?00S,S?11S,S?00,S?11}，S)。 1172.2 形式定义约定⑴ 对一组有相同左部的产生式α?β 1,α?β 2,…,α?β n可以简单地记为：α?β 1|β 2|… |β n读作,α 定义为 β 1，或者 β 2,…,或者 β n。并且称它们为 α 产生式。 β 1,β 2,…,β n称为候选式 (candidate)。 1182.2 形式定义⑵ 使用符号英文字母表较为前面的大写字母，如 A,B,C,…表示语法变量；英文字母表较为前面的小写字母,如 a,b,c,…表示终极符号；英文字母表较为后面的大写字母,如 X,Y,Z,…表示该符号是语法变量或者终极符号；英文字母表较为后面的小写字母,如 x,y,z,…表示由终极符号组成的行；希腊字母 α,β,γ … 表示由语法变量和终极符号组成的行 1192.2 形式定义例 2-3 四元组是否满足文法的要求。C ({A,B,C,E},{a,b,c},{S?ABC|abc,D?e|a，FB?c,A?A,E? abc|ε },S)C 4种修改(1) ({A,B,C,E,S,D,F},{a,b,c,e}，{S?ABC|abc,D?e|a,FB?c,A?A,E? abc|ε }，S)。(2) ({A,B,C,E,S },{a,b,c},{S?ABC|abc，A?A,E? abc|ε },S)。(3) ({A,B,C,E},{a,b,c},{ A?A,E?abc|ε },A)。(4) ({A,B,C,E},{a,b,c},{ A?A,E?abc|ε },E)。 1202.2 形式定义推导 (derivation)设 G=(V,T,P,S)是一个文法，如果 α?β ∈ P，γ,δ ∈ (V∪ T)*，则称 γ α δ 在 G中直接推导出 γ β δ 。γ α δ?G γ β δ读作,γ α δ 在文法 G中直接推导出 γ β δ 。,直接推导,可以简称为 推导 (derivation)，也称推导为 派生。 1212.2 形式定义归约 (reduction)C γ α δ?G γ β δC 称 γ β δ 在文法 G中直接归约成 γ α δ 。在不特别强调归约的直接性时,,直接归约,可以简称为 归约。 1222.2 形式定义1,推导与归约表达的意思的异同 。2,推导与归约和产生式不一样 。 所以,?G和?所表达的意思不一样 。3,推导与归约是一一对应的 。4,推导与归约的作用 。 1232.2 形式定义G,?G+,?G*当成 (V∪ T)*上的二元关系。(1)α?Gn β,表示 α 在 G中经过 n步推导出 β ；β 在 G中经过 n步归约成 α 。即，存在 α 1，α 2,…,α n-1∈ (V∪ T)*使得 α?G α 1，α 1?G α 2,…,α n-1?G β 。(2)当 n=0时，有 α =β 。即 α?G0 α 。(3)α?G+ β,表示 α 在 G中经过至少 1步推导出 β ； β 在 G中经过至少 1步归约成 α 。 1242.2 形式定义(4)α?G* β,表示 α 在 G中经过若干步推导出 β ； β 在 G中经过若干步归约成 α 。分别用?,?+,?*,?n代替G,?G+,?G*,?Gn 。 1252.2 形式定义例 2-4 设 G=({A},{a},{A?a|aA},A)A? aA 使用产生式 A?aAaaA 使用产生式 A?aAaaaA 使用产生式 A?aAaaaaA 使用产生式 A?aA…a… aA 使用产生式 A?aAa… aa 使用产生式 A?a? 1262.2 形式定义A? aA 使用产生式 A?aAaaA 使用产生式 A?aAaaaA 使用产生式 A?aAaaaaA 使用产生式 A?aA…a… aA 使用产生式 A?aAa… aaA 使用产生式 A?aA 1272.2 形式定义AAaaAAA? AAaaAaAA 使用产生式 A?aAAaAaaAaAA 使用产生式 A?aAAaAaaAaaA 使用产生式 A?aaaAaaAaaA 使用产生式 A?aaaAaaAaaa 使用产生式 A?aaaaAaaAaaa 使用产生式 A?aAaaaaaaAaaa 使用产生式 A?aaaaaaaaaaa 使用产生式 A?a 1282.2 形式定义例 2-5 设 G=({S,A,B},{0,1}，{S?A|AB,A?0|0A,B?1|11},S)对于 n? 1，A?n 0n 首先连续 n-1次使用产生式；A?0A,最后使用产生式 A?0；A?n 0nA 连续 n次使用产生式 A?0A；B? 1 使用产生式 B?1；B? 11 使用产生式 B?11。 1292.2 形式定义语 法 范 畴 A 代表的集合 L(A)={0,00,000,0000,…… }={0n|n? 1}；语法范畴 B代表的集合 L(B)={1,11}语法范畴 S代表的集合 L(S)=L(A)∪ L(A)L(B)={0,00,000,0000,… }∪ {0,00,000,0000,… }{1,11}={0,00,000,0000,… }∪∪ {01,001,,… }∪∪ {011,,000011,… } 1302.2 形式定义例 2-6 设 G=({A},{0,1},{A?01,A?0A1},A)，A?n 0nA1n n? 00nA1n? 0n+1A1n+1 n? 00nA1n? 0n+11n+1 n? 00nA1n?i 0n+iA1n+i n? 0,i? 00nA1n?i 0n+i1n+I n? 0,i? 00nA1n?* 0mA1m n? 0,m? n0nA1n?+ 0m1m n? 0,m? n+10nA1n?+ 0mA1m n? 0,m? n+10nA1n?+ 0m1m n? 0,m? n+1 1312.2 形式定义几点结论C 对任意的 x∈∑ +，我们要使语法范畴 D代表的集合为 {xn|n? 0}，可用产生式组 {D?ε |xD}来实现。C 对任意的 x,y∈∑ +，我们要使语法范畴 D代表的集合为 {xnyn|n? 1}，可用产生式组{D?xy|xDy}来实现。C 对任意的 x,y∈∑ +，我们要使语法范畴 D代表的集合为 {xnyn|n? 0}，可用产生式组{D?ε |xDy}来实现。 1322.2 形式定义语言 (language)L(G)={w | w∈ T*且 S?* w}句子 (sentence)w∈ L(G),w称为 G产生的一个 句子。句型 (sentential form)G=(V,T,P,S)，对于?α ∈ (V∪ T)*，如果 S* α,则称 α 是 G产生的一个 句型。 1332.2 形式定义句子 w是从 S开始，在 G中可以推导出来的终极符号行，它 不含 语法变量。句型 α 是从 S开始，在 G中可以推导出来的符号行，它 可能含有 语法变量。例 2-7 给定文法 G=({S,A,B,C,D},{a，b,c,d,#},{S?ABCD|abc#,A?aaA，AB?aabbB,BC?bbccC,cC?cccC，CD?ccd#,CD?d#,CD?#d},S) 1342.2 形式定义S? ABCD 使用产生式 S?ABCDaaABCD 使用产生式 A?aaAaaaaABCD 使用产生式 A?aaAaaaaaabbBCD 使用产生式 AB?aabbBaaaaaabbbbccCD 使用产生式 BC?bbccCaaaaaabbbbccccCD 使用产生式 cC?cccCaaaaaabbbbcccc#d 使用产生式 CD?#d 1352.2 形式定义S? ABCD 使用产生式 S?ABCDAbbccCD 使用产生式 BC?bbccCaaAbbccCD 使用产生式 A?aaAaaAbbccccd# 使用产生式 CD?ccd#aaaaAbbccccd# 使用产生式 A?aaAaaaaaaAbbccccd# 使用产生式 A?aaAaaaaaaaaAbbccccd# 使用产生式 A?aaA 1362.2 形式定义例 2-8 构造产生标识符的文法G=({&标识符 &,&大写字母 &,&小写字母 &,&阿拉伯数字 &},{0，1,…,9,A,B,C,…,Z,a,b,c,…,z},P,&标识符 &)P={ &标识符 &?&大写字母 &|&小写字母 &，&标识符 &?&标识符 &&大写字母 &|&标识符 &&小写字母 &|&标识符 &&阿拉伯数字 &，&大写字母 &?A|B|C|D|E|F|G|H|I|J|K|L|M|N|O，&大写字母 &?P|Q|R|S|T|U|V|W|X|Y|Z,&小写字母 &?a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z,&阿拉伯数字 &?0|1|2|3|4|5|6|7|8|9 } 1372.2 形式定义G′ =({&标识符 &,&头 &,&尾 &},{0,1，2,…,9,A,B,C,…,Z,a,b，c,…,z},P′,&标识符 &)P′ ={&标识符 &?&头 &&尾 &，&头 &?A|B|C|D|E|F|G|H|I|J|K|L|M|N&头 &?O|P|Q|R|S|T|U|V|W|X|Y|Z,&头 &?a|b|c|d|e|f|g|h|i|j|k|l|m|n&头 &?o|p|q|r|s|t|u|v|w|x|y|z, 1382.2 形式定义&尾 &?ε |0&尾 &|1&尾 &|2&尾 &|3&尾 &|4&尾 &|5&尾 &,&尾 &? 6&尾 &|7&尾 &|8&尾 &|9&尾 &,&尾 &?A&尾 &|B&尾 &|C&尾 &|D&尾 &|E&尾 &|F&尾 &，&尾 &?G&尾 &|H&尾 &|I&尾 &|J&尾 &|K&尾 &,&尾 &?L&尾 &|M&尾 &|N&尾 &|O&尾 &|P&尾 &|Q&尾 &，&尾 &? R&尾 &|S&尾 &|T&尾 &|U&尾 &|V&尾 &,&尾 &? W&尾 &|X&尾 &|Y&尾 &|Z&尾 &|a&尾 &|b&尾 &，&尾 &?c&尾 &|d&尾 &|e&尾 &|f&尾 &|g&尾 &,&尾 &?h&尾 &|i&尾 &|j&尾 &|k&尾 &|l&尾 &|m&尾 &，&尾 &? n&尾 &|o&尾 &|p&尾 &|q&尾 &|r&尾 &,&尾 &?s&尾 &|t&尾 &|u&尾 &|v&尾 &|w&尾 &|x&尾 &&尾 &?y&尾 &|z&尾 & } 1392.2 形式定义&标识符 &?&标识符 &&阿拉伯数字 &&标识符 &3&标识符 &&阿拉伯数字 &3&标识符 &23&标识符 &&小写字母 &23&标识符 &n23&标识符 &&阿拉伯数字 &n23&标识符 &8n23&标识符 &&小写字母 &8n23&标识符 &d8n23&小写字母 &d8n23id8n23 1402.2 形式定义标识符 &?&头 &&尾 &i&尾 &id&尾 &id8&尾 &id8n&尾 &id8n2&尾 &id823&尾 &id8n23 1412.2 形式定义使用符号使文法更简洁G′′=({&标识符 &},{b,a,d},{&标识符 &?b|a|&标识符 &b|&标识符 &a|&标识符 &d},&标识符 &)G′′′=({L},{b,a,d},{L?b|a|Lb|La|Ld},L)G′′′′=({L,H,T},{ b,a,d },{L?HT，H?b|a,T?ε |bT|aT|dT},L) 1422.3 文法的构造例 2-9 构造文法 G，使 L(G)={0,1,00,11}C 将文法的开始符号定义为这 4个句子。G1=({S},{0,1},{S?0,S?1,S?00,S?11},S)C 先用变量 A表示 0，用变量 B表示 1。G2=({S,A,B},{0,1},{S?A,S?B,S?AA，S?BB,A?0,B?1},S)C 基于 G2，考虑,规范性,问题。G3=({S,A,B},{0,1},{S?0,S?1,S?0A，S?1B,A?0,B?1},S) 1432.3 文法的构造C 可以在 V,T中增加一些元素，以获得,不同的,文法。G4=({S,A,B,C},{0,1,2},{S?A,S?B，S?AA,S?BB,A?0,B?1},S)G5=({S,A,B,C},{0,1,2},{S?A,S?B，S?AA,S?BB,A?0,B?1,CACS?21，C?11,C?2},S)L(G1)= L(G2)= L(G3)= L(G4)= L(G5) 1442.3 文法的构造等价 (equivalence)C 设有两个文法 G1和 G2，如果 L(G1)= L(G2)，则称 G1与 G2等价。约定C 对一个文法，只列出该文法的所有产生式，且所列第一个产生式的左部是该文法的开始符号。 1452.3 文法的构造G1,S?0|1|00|11G2,S?A|B|AA|BB,A?0,B?1G3,S?0|1|0A|1B,A?0,B?1G4,S?A|B|AA|BB,A?0,B?1G5,S?A|B|BB,A?0,B?1,CACS?21，C?11,C?2 1462.3 文法的构造例 2-10L={0n|n? 1}G6,S?0|0SL={0n|n? 0}G7,S?ε |0SL={02n13n|n? 0}G8,S?ε |00S111 1472.3 文法的构造例 2-11 构造文法 G9，使 L(G9)={w|w∈ {a,b,…,z}+}。G9,S?A|ASA?a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z用 S?A|AS生成 An。不可以用 A?a|b|c|…|z 表示。A?a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z不可以用 A?a8表示 A?aaaaaaaa。不能用 A?an 表示 A可以产生任意多个 a。 1482.3 文法的构造例 2-12 构造文法 G10，使L(G10)={wwT|w∈ {0,1,2,3}+}。文法S?HEH?0|1|2|3|0H|1H|2H|3HE?0|1|2|3|E0|E1|E2|E3难以生成 L(G10)。 1492.3 文法的构造{wwT|w∈ {0,1,2,3}+}的句子的特点设 w=a1a2… an，从而有 wT= an… a2 a1,故 wwT= a1a2… anan… a2 a1满足 f(w wT,i)=f(w wT,|w wT|-i+1)。递归地定义 LC ⑴ 对?a∈ {0,1,2,3},aa∈ L；C ⑵ 如果 x∈ L,则对?a∈ {0,1,2,3},axa∈ L；C ⑶ L中不含不满足 (1),(2)任何其他的串。 1502.3 文法的构造根据递归定义中的第一条,有如下产生式组：S?00 | 11 | 22 | 33再根据递归定义第二条,又可得到如下产生式组：S?0S0 | 1S1 | 2S2 | 3S3从而,G10,S?00 | 11 | 22 | 33 | 0S0 | 1S1 | 2S2 | 3S3 1512.3 文法的构造例 2-13 构造文法 G12，使 L(G12)={w|w是我们习惯的十进制有理数 }。G12,S?R | +R | -RR?N | BB?N.DN?0 | AMD?0 | MAA?1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9M?ε | 0M | 1M | 2M | 3M | 4M | 5M | 6M | 7M | 8M | 9M 1522.3 文法的构造例 2-14 构造产生算术表达式的文法：⑴ 基础：常数是算术表达式,变量是算术表达式；⑵ 归纳：如果 E1,E2是表达式,则 +E1,-E1、E1+E2,E1-E2,E1*E2,E1/E2,E1**E2,Fun(E1)是算术表达式 。 其中 Fun为函数名 。⑶ 只有满足 (1)和 (2)的才是算术表达式。G13,E?id|c|+E|-E|E+E|E-E|E*E|E/E|E**E|Fun(E) 1532.3 文法的构造例 2-15 构造产生语言 {anbncn|n? 1}的文法。文法 G=({S1},{a,b},{S1?ab | aS1b},S1)产生的语言 {anbn | n? 1}形式上看起来与语言{anbncn| n? 1}比较接近 。G=({S2},{c},{S2?c | cS2},S2)产生的语言是 {cn|n? 1}。{anbncn | n? 1}≠{a nbn | n? 1}{cn | n? 1} 1542.3 文法的构造文法S?S1S2S1?ab | aS1bS2?c | cS2不能产生语言{anbncn | n? 1}而是产生语言{anbn | n?1}{c n | n?1} 1552.3 文法的构造文法G,S?abc | aSbc产生的语言为：{an(bc)n | n? 1}焦点：交换 b和 c的位置。 1562.3 文法的构造G14,S?aBC | aSBC，CB?BCaB?abbB?bbbC?bccC?ccG14′,S?abc|aSBc，bB?bbcB?Bc 157文法的乔姆斯基体系文法 G=(V,T,P,S)G叫做 0型文法 (type 0 grammar)，也叫做短语结构文法 (phrase structure grammar,PSG)。L(G)叫做 0型语言 。也可以叫做 短语结构语言 (PSL)、递归可枚举集 (recursivelyenumerable,r.e,)。 158文法的乔姆斯基体系G是 0型文法。如果对于?α?β ∈ P，均有 |β |? |α |成立，则称 G为 1型文法 (type 1 grammar)，或 上下文有关文法 (context sensitivegrammar,CSG)。L(G)叫做 1型语言 (type 1 language)或者上下文有关语言 (context sensitivelanguage,CSL)。 159文法的乔姆斯基体系G是 1型文法如果对于?α?β ∈ P，均有 |β |? |α |，并且α ∈ V成立，则称 G为 2型文法 (type 2grammar)，或 上下文无关文法 (context freegrammar,CFG)。L(G)叫做 2型语言 (type 2 language)或者 上下文无关语言 (context free language,CFL)。 160文法的乔姆斯基体系G是 2型文法如果对于?α?β ∈ P,α?β 均具有形式A?wA?wB其中 A,B∈ V,w∈ T+。 则称 G为 3型文法(type 3 grammar),也可称为 正则文法(regular grammar,RG)或者正规文法 。L(G)叫做 3型语言 (type 3 language),也可称为 正 则 语 言 或者 正 规 语 言 (regularlanguage,RL)。 161文法的乔姆斯基体系⑴ 如果一个文法 G是 RG,则它也是 CFG、CSG和短语结构文法 。 反之不一定成立 。⑵ 如果一个文法 G是 CFG,则它也是 CSG和短语结构文法 。 反之不一定成立 。⑶ 如果一个文法 G是 CSG,则它也是短语结构文法 。 反之不一定成立 。相应地：⑷ RL也是 CFL,CSL和短语结构语言 。 反之不一定成立 。 162文法的乔姆斯基体系⑸ CFL也是 CSL和短语结构语言 。 反之不一定成立 。⑹ CSL也是短语结构语言 。 反之不一定成立⑺ 当文法 G是 CFG时,L(G)却可以是 RL。⑻ 当文法 G是 CSG时,L(G)可以是 RL,CSL。⑼ 当文法 G是短语结构文法时,L(G)可以是RL,CSL和 CSL。 163文法的乔姆斯基体系定理 2-1 L是 RL的充要条件是存在一个文法，该文法产生语言 L，并且它的产生式要么是形如,A?a的产生式，要么是形如 A?aB的产生式。其中 A,B为语法变量,a为终极符号。证明,C 充分性：设有 G′,L(G′ )=L，且 G′ 的产生式的形式满足定理要求。这种文法就是 RG。所以，G′ 产生的语言就是 RL，故 L是 RL。 164文法的乔姆斯基体系必要性构造：用 产生式组：A?a1A1A1?a2A2…An-1?an代替产生式A? a1a2… an 165文法的乔姆斯基体系用 产生式组A?a1A1A1?a2A2…An-1?anB代替产生式A? a1a2… an B 166文法的乔姆斯基体系证明 L(G′ )=L(G) 。施归纳于推导的步数，证明一个更一般的结论：对于?A∈ V,A?G+ x?A?G′ + x。因为 S∈ V，所以结论自然对 S成立。 167文法的乔姆斯基体系几点注意事项⑴ 我们是按照 RG的一般定义来构造一个与之等价的文法的,这与读者以前熟悉的根据一个具体的对象构造另一个对象是不同的 。 在这里,可以使用的是非常一般的条件 ――一个一般模型 。 这也是这类问题的证明所要求的 。 而且在本书的后面,将会有更多这样的情况 。 168文法的乔姆斯基体系⑵ 为了证明一个特殊的结论,可以通过证明一个更为一般的结论来完成 。 这从表面上好像是增加了我们要证明的内容,但实际上它会使我们能够更好地使用归纳假设,以便顺利地获得我们所需要的结论 。 169文法的乔姆斯基体系⑶ 施归纳于推导的步数是证明本书中不少问题的较为有效的途径 。 有时我们还会对字符串的长度施归纳 。本证明的主要部分含两个方面,首先是构造,然后对构造的正确性进行证明 。 这种等价性证明的思路是非常重要的 。 170文法的乔姆斯基体系线性文法 (liner grammar)C 设 G=(V,T,P,S),如果对于?α?β ∈ P，α?β 均具有如下形式：C A?wC A?wBxC 其中 A,B∈ V,w,x∈ T*，则称 G为 线性文法。线性语言 (liner language)C L(G)叫做 线性语言 171文法的乔姆斯基体系右线性文法 (right liner grammar)C 设 G=(V,T,P,S),如果对于?α?β ∈ P，α?β 均具有如下形式：C A?wC A?wBC 其中 A,B∈ V,w,x∈ T*，则称 G为 线性文法。右线性语言 (right liner language)C L(G)叫做右 线性语言。 172文法的乔姆斯基体系左线性文法 (left liner grammar)C 设 G=(V,T,P,S),如果对于?α?β ∈ P，α?β 均具有如下形式：C A?wC A?BwC 其中 A,B∈ V,w,x∈ T*，则称 G为 线性文法。左线性语言 (left liner language)C L(G)叫做右 线性语言。 173文法的乔姆斯基体系定理 2-2 L是一个左线性语言的充要条件是存在文法 G,G中的产生式要么是形如,A?a的产生式，要么是形如 A?Ba的产生式，使得 L(G)=L。其中 A,B为语法变量,a为终极符号。 174文法的乔姆斯基体系定理 2-3 左线性文法与右线性文法等价。按照定理 2-1的证明经验,要想证明本定理,需要完成如下工作：C 对任意右线性文法 G,我们能够构造出对应的左线性文法 G′,使得 L(G′ )=L(G)；C 对任意左线性文法 G,我们能够构造出对应的右线性文法 G′,使得 L(G′ )=L(G)。 175文法的乔姆斯基体系例 2-17 语言 {0123456}的左线性文法和右线性文法的构造。右线性文法Gr,Sr?0ArAr?1BrBr?2CrCr?3DrDr?4ErEr?5FrFr?6 176文法的乔姆斯基体系0123456在文法 Gr中的推导Sr?0Ar 使用产生式 Sr?0Ar01Br 使用产生式 Ar?1Br012Cr 使用产生式 Br?2Cr0123Dr 使用产生式 Cr?3Dr01234Er 使用产生式 Dr?4Er012345Fr 使用产生式 Er?5Fr0123456 使用产生式 Fr?6 177文法的乔姆斯基体系左线性文法Gl,Sl?Al6Al?Bl5Bl?Cl4Cl?Dl3Dl?El2El?Fl1Fl?0 178文法的乔姆斯基体系 179文法的乔姆斯基体系0123456在文法 Gl中的推导Sl?Al6 使用产生式 Sl?Al6Bl56 使用产生式 Al?Bl5Cl456 使用产生式 Bl?Cl4Dl3456 使用产生式 Cl?Dl3El23456 使用产生式 Dl?El2Fl1234456 使用产生式 El?Fl10123456 使用产生式 Fl?0 180文法的乔姆斯基体系0123456被归约成文法 Gl的开始符号 S0123456Fl1234456 使用产生式 Fl?0El23456 使用产生式 El?Fl1Dl3456 使用产生式 Dl?El2Cl456 使用产生式 Cl?Dl3Bl56 使用产生式 Bl?Cl4Al6 使用产生式 Al?Bl5Sl 使用产生式 Sl?Al6 181文法的乔姆斯基体系 182文法的乔姆斯基体系定理 2-4 左线性文法的产生式与右线性文法的产生式混用所得到的文法不是 RG。证明：设有文法G15,S?0AA?S1|1不难看出,L(G15)={0n1n|n? 1}。我们构造不出RG G，使得 L(G)= L(G15)={0n1n|n? 1}。因为L(G15)={0n1n|n? 1}不是 RL。所以,G15不是 RG。有关该语言不是 RL的证明我们将留到研究 RL的性质时去完成。 1832.5 空语句形如 A?ε 的产生式叫做空产生式，也可叫做 ε 产生式。在 RG,CFG,CSG中，都不能含有空产生式。所以，任何 CSL中都不含有空语句 ε 。从而 CFL和 RL中都不能含空语句 ε 。空语句 ε 在一个语言中的存在并不影响该语言的有穷描述的存在性，甚至除了为生成空语句 ε 外，空产生式可以不被用于语言中其他任何句子的推导中。 1842.5 空语句允许 CSL,CFL,RL包含空语句 ε 后，还会给我们进行问题的处理提供一些方便。允许在 RG,CFG,CSG中含有空产生式允许 CSL,CFL,RL包含空语句 ε 。 1852.5 空语句定理 2-5 设 G=(V,T,P,S)为一文法，则存在与 G同类型的文法 G′ =(V′,T,P′,S′ )，使得L(G)=L(G′ )，但 G′ 的开始符号 S′ 不出现在 G′的任何产生式的右部。证明：构造当文法 G=(V,T,P,S)的开始符号 S不出现在 P中的任何产生式的右部时,G就是所求G′=(V∪ {S′},T,P′,S′)P′ =P∪ {S′?α |S?α ∈ P} 1862.5 空语句证明 L(G)?L(G′ )对任意的 x∈ L(G′ ),由文法产生的语言的定义知,在 G′ 中存在如下推导：S′?α 使用产生式 S′?α*x 使用 P′ 中的除 S′?α 以外的其他产生式。在推导 α?*x中使用的产生式都是 P中的产生式。因此，推导 α?*x在 G中仍然成立。 1872.5 空语句由 P′ 的定义知，必有 S?α ∈ P所以，S?α 使用 P中的产生式 S?α*x 使用 P中的产生式故，L(G′ )?L(G) 1882.5 空语句设 G中存在如下推导：S?α 使用 P中的产生式 S?α*x 使用 P中的产生式由 P′ =P∪ {S′?α |S?α ∈ P },知道 G′ 中,S′?α 使用产生式 S′?α*x 使用 P′ 所包含的 P中的其他产生式。故,L(G)?L(G′ )。 1892.5 空语句设 G=(V,T,P,S)是一个文法，如果 S不出现在 G的任何产生式的右部，则：⑴ 如果 G是 CSG,则仍然称 G=(V,T,P∪ {S?ε }，S)为 CSG； G产生的语言仍然称为 CSL。⑵ 如果 G是 CFG,则仍然称 G=(V,T,P∪ {S?ε }，S)为 CFG； G产生的语言仍然称为 CFL。⑶ 如果 G是 RG,则仍然称 G=(V,T,P∪ {S?ε }，S)为 RG。 G产生的语言仍然称为 RL。 1902.5 空语句定理 2-6下列命题成立：⑴ 如果 L是 CSL,则 L∪ {ε }仍然是 CSL。⑵ 如果 L是 CFL,则 L∪ {ε }仍然是 CFL。⑶ 如果 L是 RL,则 L∪ {ε }仍然是 RL。 1912.5 空语句证明：对第 1个命题：设 L是 CSL,则存在一个 CSG G=(V,T,P,S),使得 L(G)=L。由定理 2-5-1,我们不妨假设 S不出现在 G的任何产生式的右部 。取：G′ =(V,T,P∪ {S?ε },S)由于 S不出现在 G的任何产生式的右部,所以,S?ε 不可能出现在任何长度不为 0的句子的推导中 。 1922.5 空语句易证：L(G′ )=L(G)∪ {ε }。由于 G′ 是 CSG，所以,L(G)∪ {ε }是 CSL。同理可证第 2和第 3个命题。 1932.5 空语句定理 2-7 下列命题成立⑴ 如果 L是 CSL,则 L-{ε }仍然是 CSL。⑵ 如果 L是 CFL,则 L-{ε }仍然是 CFL。⑶ 如果 L是 RL，则 L-{ε }仍然是 RL。 1942.5 空语句证明：对第 1个命题：设 L是 CSL,则存在一个 CSG G=(V,T,P,S),使得 L(G)=L。如果 ε?L,则 L-{ε }=L,所以,L-{ε }是CSL。如果 ε ∈ L,由定理 2-5-1,我们不妨假设 S不出现在 G的任何产生式的右部 。 取：G′ =(V,T,P-{S?ε },S) 1952.5 空语句由于 S不出现在 G的任何产生式的右部,所以,如果 L(G)中存在长度非 0的句子,S?ε 不可能出现在它们的推导中 。 也就是说,将S?ε 从 G中去掉后,不会影响 L(G)中任何长度非 0的句子的推导 。 容易证明：L(G′ )=L(G)-{ε }由于 G′ 是 CSG,所以,L(G)-{ε }是 CSL。同理可证其他两个命题。 1962.5 空语句对于任意文法 G=(V,T,P,S)，对于 G中的其他变量 A，出现形如 A?ε 的产生式是不会改变文法产生的语言的类型的，而且这样一来，对我们进行文法的构造等工作还提供了很多方便。所以，我们约定：对于 G中的任何变量 A，在需要的时候，可以出现形如 A?ε 的产生式。 1972.6 小结本章讨论了语言的文法描述。首先介绍文法的基本定义和推导、归约、文法定义的语言、句子、句型、文法的等价等重要概念。讨论了如何根据语言的特点、通过用语法变量去表示适当的集合（语法范畴）的方法进行文法构造，并按照乔姆斯基体系，将文法划分成 PSG,CSG,CFG、RG等 4类。在这些文法中，线性文法是一类重要的文法。 1982.6 小结⑴ 文法 G=(V,T,P,S)。 任意 A∈ V表示集合 L(A)={w | w∈ T*且 A?* w}。⑵ 推导与归约 。 文法中的推导是根据文法的产生式进行的 。 如果 α?β ∈ P,γ,δ ∈ (V∪ T)*,则称 γ α δ 在 G中直接推导出 γ β δ,γ α δ?G γ β δ ；也称γ β δ 在文法 G中直接归约成 γ α δ 。 1992.6 小结⑶ 语言,句子和句型 。 文法 G产生的语言L(G)={w | w∈ T*且 S?* w},w∈ L(G)为句子 。 一般地,由开始符号推出来的任意符号行叫做 G的句型 。⑷ 一个语言可以被多个文法产生,产生相同语言的文法被称是等价的 。 2002.6 小结⑸ 右线性文法的产生式都可以是形如 A?a和A?aB的产生式。左线性文法的产生式都可以是形如 A?a和 A?Ba的产生式。左线性文法与右线性文法是等价的。然而，左线性文法的产生式与右线性文法的产生式混用所得到的文法不是正则文法。 201第 3章 有穷状态自动机主要内容确定的有穷状态自动机 (DFA)C 作为对实际问题的抽象,直观物理模型,形式定义,DFA接受的句子,语言,状态转移图 。不确定的有穷状态自动机 (NFA)C 定义；C NFA与 DFA的等价性； 202第 3章 有穷状态自动机带空移动的有穷状态自动机 (ε-NFA)C 定义 。C ε-NFA与 DFA的等价性 。FA是正则语言的识别器C 正则文法 (RG)与 FA的等价性 。C 相互转换方法 。C 带输出的有穷状态自动机 。C 双向有穷状态自动机 。 203第 3章 有穷状态自动机重点,DFA的概念,DFA,NFA,ε-NFA,RG之间的等价转换思路与方法 。难点：对 DFA概念的理解,DFA,RG的构造方法,RG与 FA的等价性证明 。 2043.1 语言的识别推导和归约中的回溯问题将对系统的效率产生极大的影响S?aA|aBA?aA|cB?aB|d分析句子 aaac的过程中可能需要回溯 。 2053.1 语言的识别系统识别语言 {anc|n≥1}∪ {and|n≥1}的字符串过程中状态的变化图示如下： 2063.1 语言的识别识别系统 (模型 )⑴ 系统具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。⑵ 我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。 2073.1 语言的识别⑶ 系统在任何一个状态 (当前状态 )下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。当前状态和新的状态可以是同一个状态，也可以是不同的状态；当系统从输入字符串中读入一个字符后，它下一次再读时，会读入下一个字符。这就是说，相当于系统维持有一个读写指针，该指针在系统读入一个字符后指向输入串的下一个字符。 2083.1 语言的识别⑷ 系统中有一个状态，它是系统的开始状态，系统在这个状态下开始进行某个给定句子的处理。⑸ 系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子，把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。 2093.1 语言的识别相应的物理模型一个右端无穷的输入带。一个有穷状态控制器 (finite state control,FSC) 。一个读头。系统的每一个动作由三个节拍构成：读入读头正注视的字符；根据当前状态和读入的字符改变有穷控制器的状态；将读头向右移动一格。 2103.1 语言的识别有穷状态自动机的物理模型 2113.2有穷状态自动机有穷状态自动机 (finite automaton,FA)M=(Q,∑,δ,q0,F)Q――状态的非空有穷集合 。q∈ Q,q称为M的一个 状态 (state)。∑――输入字母表 (Input alphabet)。输入字符串都是 ∑上的字符串。q0――q0∈ Q,是 M的 开始状态 (initial state)，也可叫做初始状态或者启动状态 。 2123.2有穷状态自动机δ――状态 转移函数 (transition function)，有时候又叫做状态转换函数或者移动函数。δ,Q&#215; ∑?Q，对?(q,a)∈ Q&#215; ∑,δ(q，a)=p表示,M在状态 q读入字符 a，将状态变成 p，并将读头向右移动一个带方格而指向输入字符串的下一个字符。F――F?Q，是 M的 终止状态 (final state)集合。q∈ F,q称为 M的 终止状态,又称为接受状态 (accept state)。 2133.2有穷状态自动机例 3-1 下面是一个有穷状态自动机M1=({q0,q1,q2},{0},δ1,q0,{q2})其中,δ1(q0,0)= q1,δ1(q1,0)= q2,δ1(q2,0)= q1用表 3-1表示 δ1。状态说明 状态 输入字符0开始状态 q0 q1q1 q2终止状态 q2 q1 2143.2有穷状态自动机M2=({q0,q1,q2,q3},{0,1,2},δ 2,q0,{q2})δ 2(q0,0)= q1,δ 2(q1,0)= q2δ 2(q2,0)= q1,δ 2(q3,0)= q3δ 2(q0,1)= q3,δ 2(q1,1)= q3δ 2(q2,1)= q3,δ 2(q3,1)= q3δ 2(q0,2)= q3,δ 2(q1,2)= q3δ 2(q2,2)= q3,δ 2(q3,2)= q3 2153.2有穷状态自动机状态说明 状态 输入字符0 1 2开始状态 q0 q1 q3 q3q1 q2 q3 q3终止状态 q2 q1 q3 q3q3 q3 q3 q3表 3-2 δ 2转换函数 2163.2有穷状态自动机将 δ 扩充为QQ *:对任意的 q∈ Q,w∈∑ *,a∈∑,定义)),,(?(),(?)2(),(?)1(awqwaqqq 2173.2有穷状态自动机),()),,(?(),(?),(?aqaqaqaq两值相同，不用区分这两个符号。 2183.2有穷状态自动机确定的有穷状态自动机C 由于对于任意的 q∈ Q,a∈∑,δ (q,a)均有确定的值，所以，将这种 FA称为 确定的有穷状态自动机 (deterministic finite automaton，DFA) 2193.2有穷状态自动机M接受 (识别 )的语言对于?x∈∑ *如果 δ (q,w)∈ F,则称 x被 M接受,如果 δ (q,w)?F,则称 M不接受 x。L(M)={x| x∈∑ *且 δ (q,w)∈ F}称为由 M接受 (识别 )的语言L(M1)= L(M2)={02n|n? 1}如果 L(M1)=L(M2)，则称 M1与 M2等价。 2203.2有穷状态自动机例 3-2 构造一个 DFA，它接受的语言为{x000y|x,y∈ {0,1}*}q0――M的启动状态；q1――M读到了一个 0,这个 0可能是子串,000”的第 1个 0；q2――M在 q1后紧接着又读到了一个 0,这个 0可能是子串,000”的第 2个 0；q3――M在 q2后紧接着又读到了一个 0,发现输入字符串含有子串,000”；因此,这个状态应该是终止状态 。 2213.2有穷状态自动机δ (q0,1)= q0――M在 q0读到了一个 1,它需要继续在 q0,等待,可能是子串,000”的第 1个 0的输入字符 0；δ (q1,1)= q0――M在刚刚读到了一个 0后,读到了一个 1,表明在读入这个 1之前所读入的 0并不是子串,000”的第 1个 0,因此,M需要重新回到状态 q0,以寻找子串,000”的第 1个 0； 2223.2有穷状态自动机δ (q2,1)= q0――M在刚刚发现了 00后,读到了一个 1,表明在读入这个 1之前所读入的 00并不是子串,000”的前两个 0,因此,M需要重新回到状态 q0,以寻找子串,000”的第 1个 0；δ (q3,0)= q3――M找到了子串,000”,只用读入该串的剩余部分 。δ (q3,1)= q3――M找到了子串,000”,只用读入该串的剩余部分 。 2233.2有穷状态自动机M=({q0,q1,q2,q3},{0,1},{ (q0,0)= q1，δ (q1,0)= q2,δ (q2,0)= q3,δ (q0,1)= q0，δ (q1,1)= q0,δ (q2,1)= q0,δ (q3,0)= q3，δ (q3,1)= q3},q0,{q3})状态说明 状态 输入字符0 1开始状态 q0 q1 q0q1 q2 q0q2 q3 q0终止状态 q3 q3 q3 2243.2有穷状态自动机一种更为直观的表示 2253.2有穷状态自动机状态转移图 (transition diagram)⑴ q∈ Q? q是该有向图中的一个顶点；⑵ δ (q,a)=p? 图中有一条从顶点 q到顶点 p的标记为 a的弧；⑶ q∈ F? 标记为 q的顶点被用双层圈标出；⑷ 用标有 S的箭头指出 M的开始状态 。状态转移图又可以叫做 状态转换图。 2263.2有穷状态自动机例 3-3构造一个 DFA，它接受的语言为{x000|x∈ {0,1}*}。C 状态 q0读到的 0可能是输入字符串的最后三个 0的第 1个 0；C 在状态 q1紧接着读到的 0可能是输入字符串的最后三个 0的第 2个 0；C 在状态 q2紧接着读到的 0可能是输入字符串的最后三个 0的第 3个 0； 2273.2有穷状态自动机C 在状态 q3紧接着读到的 0也可能是输入字符串的最后三个 0的第 3个 0；C 如果在状态 q1,q2,q3读到的是 1，则要重新检查输入串是否以三个 0结尾。 2283.2有穷状态自动机几点值得注意⑴ 定义 FA时，常常只给出 FA相应的状态转移图就可以了。⑵ 对于 DFA来说，并行的弧按其上的标记字符的个数计算，对于每个顶点来说，它的出度恰好等于输入字母表中所含的字符的个数。 2293.2有穷状态自动机⑶ 不难看出，字符串 x被 FA M接受的充分必要条件是，在 M的状态转移图中存在一条从开始状态到某一个终止状态的有向路，该有向路上从第 1条边到最后一条边的标记依次并置而构成的字符串 x。简称此路的标记为 x。⑷ 一个 FA可以有多于 1个的终止状态。 2303.2有穷状态自动机接受语言 {x000|x∈ {0,1}*}∪ {x001|x∈ {0,1}*}的 FA 2313.2有穷状态自动机即时描述 (instantaneous description，ID ）C x,y∈∑ *,δ (q0,x)=q,xqy称为 M的一个 即时描述,表示 xy是 M正在处理的一个字符串,x引导 M从 q0启动并到达状态 q,M当前正注视着y的首字符。C 如果 xqay是 M的一个即时描述,且 δ (q,a)=p，则 xqay ├ M xapy。 2323.2有穷状态自动机α ├ Mn β,表示 M从即时描述 α 经过 n次移动到达即时描述 β 。M存在即时描述 α 1,α 2,……,α n-1，使得α ├ M α 1,α 1├ M α 2,…,α n-1├ Mβ当 n=0时，有 α =β 。即 α ├ M 0 α 。α├M + β：表示 M从即时描述 α经过至少 1次移动到达即时描述 β。α ├ M * β,表示 M从即时描述 α 经过若干步移动到达即时描述 β 。 2333.2有穷状态自动机当意义清楚时，我们将符号 ├ M,├ Mn、├ M*,├ M+中的 M省去，分别用 ├,├ n、├ *,├ +表示。 2343.2有穷状态自动机对下图所示的 DFA有如下的 ID转换： 2353.2有穷状态自动机q├ 1q├ 10q├ 101q├ ├ ├ 01├ 1├
2363.2有穷状态自动机├ ├ q0即 q├ q0q├ +q0q├ *q0 2373.2有穷状态自动机对于 x∈∑ *,q0x1├ + x1q0q0x10├ + x10q1q0x100├ + x100q2q0x000├ + x000q3 2383.2有穷状态自动机能引导 FA从开始状态到达 q的字符串的集合为：set(q)={x | x∈∑ *,δ (q0,x)=q}对图 3-3所给的 DFA中的所有 q，求 set(q)。 239set(q0)={x | x∈∑ *,x=ε 或者 x以 1结尾 }set(q1)={x | x∈∑ *,x=0或者 x以 10结尾 }set(q2)={x | x∈∑ *,x=00或者 x以 100结尾 }set(q3)={x | x∈∑ *,x以 000结尾 }set(q4)={x | x∈∑ *,x以 001结尾 }这 5个集合是两两互不相交 。 2403.2有穷状态自动机对于任意一个 FA M=(Q,∑,δ,q0,F)我们可以按照如下方式定义关系 RM：对?x,y∈∑ *,xRMyq∈ Q,使得x∈ set(q)和 y∈ set(q)同时成立 。按照这个定义所得到的关系实际上是 ∑ *上的一个等价关系。利用这个关系，可以将∑ *划分成不多于 |Q|个等价类。 2413.2有穷状态自动机例 3-4 构造一个 DFA，它接受的语言为 {0n1m2k|n,m,k? 1}。q0――M的启动状态；q1――M读到至少一个 0,并等待读更多的 0；q2――M读到至少一个 0后,读到了至少一个1,并等待读更多的 1；q3――M读到至少一个 0后跟至少一个 1后，并且接着读到了至少一个 2。 2423.2有穷状态自动机先设计“主体框架”再补充细节 2433.2有穷状态自动机⑴ 当 FA一旦进入状态 qt，它就无法离开此状态。所以,qt相当于一个陷阱状态 (trap)。一般地，我们将陷阱状态用作在其他状态下发现输入串不可能是该 FA所识别的语言的句子时进入的状态。在此状态下,FA读完输入串中剩余的字符。 2443.2有穷状态自动机⑵ 在构造一个识别给定语言的 FA时，用画图的方式比较方便、直观。我们可以先根据语言的主要特征画出该 FA的,主体框架,,然后再去考虑画出一些细节要求的内容。 2453.2有穷状态自动机⑶ FA的状态具有一定的记忆功能：不同的状态对应于不同的情况，由于 FA只有有穷个状态，所以，在识别一个语言的过程中，如果有无穷种情况需要记忆，我们肯定是无法构造出相应的 FA的。 2463.2有穷状态自动机例 3-5构造一个 DFA，它接受的语言为 {x|x∈ {0,1}*，且当把 x看成二进制数时,x模 3与 0同余 }。q0――对应除以 3余数为 0的 x组成的等价类；q1――对应除以 3余数为 1的 x组成的等价类；q2――对应除以 3余数为 2的 x组成的等价类；qs――M的开始状态 。 2473.2有穷状态自动机qs――在此状态下读入 0时，有 x=0，所以应该进入状态 q0；读入 1时，有 x=1，所以应该进入状态 q1。即,δ (qs,0)= q0； δ (qs，1)= q1 。 2483.2有穷状态自动机q0――能引导 M到达此状态的 x除以 3余 0，所以有,x=3*n+0。读入 0时,引导 M到达下一个状态的字符串为 x0,x0=2*(3*n+0)=3*2*n+0 。 所以,δ (q0,0)= q0；读入 1时,M到达下一个状态的字符串为 x1，x1=2*(3*n+0)+1=3*2*n+1。所以,δ (q0，1)= q1； 2493.2有穷状态自动机q1――能引导 M到达此状态的 x除以 3余 1，所以有,x=3*n+1。读入 0时,引导 M到达下一个状态的字符串为 x0,x0=2*(3*n+1)=3*2*n+2。 所以即：δ (q1,0)= q2；读入 1时，引导 M到达下一个状态的字符串为 x1，x1=2*(3*n+1)+1=3*2*n+2+1=3*(2*n+1)。所以 δ (q1,1)= q0 2503.2有穷状态自动机q2――能引导 M到达此状态的 x除以 3余 2,所以：x=3*n+2。读入 0时,引导 M到达下一个状态的字符串为 x0，x0=2*(3*n+2)=3*2*n+4=3*(2*n+1)+1。 所以 δ (q2，0)= q1；读入 1时，引导 M到达下一个状态的字符串为 x1，x1=2*(3*n+2)+1=3*2*n+4+1=3*(2*n+1)+2。所以，δ (q2,1)= q2 。 2513.2有穷状态自动机接受语言 {x|x∈ {0,1}*，且当把 x看成二进制数时,x模 3与 0同余 }的 DFA如下： 2523.2有穷状态自动机例 3-6 构造一个 DFA，它接受的语言L={x|x∈ {0,1}*，且对 x中任意一个长度不大于 5的子串 a1a2… an，a1+a2+… +an? 3,n? 5} 。输入串为 a1a2… ai… ai+4ai+5… am 2533.2有穷状态自动机当 i=1,2,3，也就是 M读到输入串的第 1、2,3个字符时，它需要将这些字符记下来。因为 a1…… ai可能需要用来判定输入串的最初 4~5个字符组成的子串是否满足语言的要求。当 i=4,5，也就是 M读到输入串的第 4,5个字符时，在 a1+a2+…… +ai? 3的情况下,M需要将 a1…… ai记下来；在 a1+a2+…… +ai&3时,M应该进入陷阱状态 qt。 2543.2有穷状态自动机当 i=6，也就是 M读到输入串的第 6个字符，此时，以前读到的第 1个字符 a1就没有用了，此时它要看 a2+a3+… +a6? 3是否成立，如果成立,M需要将 a2… a6记下来；在a2+a3+… +ai&3时,M应该进入陷阱状态 qt。 2553.2有穷状态自动机当 M完成对子串 a1a2… ai… ai+4的考察，并发现它满足语言的要求时,M记下来的是ai… ai+4，此时它读入输入串的第 i+5个字符ai+5，以前读到的第 i个字符 ai就没有用了，此时它要看 ai+1+ai+2+… +ai+5? 3是否成立，如果成立,M需要将 ai+1,ai+2,…,ai+5记下来；在 ai+1+ai+2+… +ai+5&3时,M应该进入陷阱状态 qt。 2563.2有穷状态自动机M需要记忆的内容有：什么都未读入 ――20=1种；记录有 1个字符 ――21=2种；记录有 2个字符 ――22=4种；记录有 3个字符 ――23=8种；记录有 4个字符 ――24-1=15种；记录有 5个字符 ――25-6=26种；记录当前的输入串不是句子 ――1种。 2573.2有穷状态自动机状态设置q[ε ]――M还未读入任何字符；qt――陷阱状态；q[a1a2… ai]――M记录有 i个字符,1? i? 5。 a1，a2,…,ai∈ {0,1}。取 DFA M=(Q,{0,1},δ,q[ε ],F)F={ q[ε ] }∪ { q[a1a2… ai]| a1,a2,…,ai∈ {0,1}且1? i? 5且 a1+a2+… +ai? 3}Q={qt }∪ F 2583.2有穷状态自动机δ (q[ε ],a1)=q[a1]δ (q[a1],a2)=q[a1a2]δ (q[a1a2],a3)=q[a1a2a3]q[a1a2a3a] 如果 a1+a2+a3+a? 3δ (q[a1a2a3],a)=qt 如果 a1+a2+a3+a&3 2593.2有穷状态自动机q[a1a2a3a4a] 如果 a1+a2+a3+a4+a? 3δ (q[a1a2a3a4],a)=qt 如果 a1+a2+a3+a4+a&3q[a2a3a4a5a] a2+a3+a4+ a5+a? 3δ (q[a1a2a3a4a5],a)=qt 如果 a2+a3+a4+ a5+a&3δ (qt,a1)=qt 2603.3 NFA3.3.1 作为对 DFA的修改希望是接受 {x|x∈ {0,1}*，且 x含有子串 00或 11}的 FA如下： 2613.3.1 作为对 DFA的修改希望是接受 {x|x∈ {0,1}*，且 x 的倒数第 10个字符为 1}的 FA如下, 2623.3.1 作为对 DFA的修改这两个图所给的,FA”与前面我们所定义的 FA,即 DFA,的区别在于：⑴ 并不是对于所有的 (q,a)∈∑ &#215; Q,δ (q，a)都有一个状态与它对应；⑵ 并不是对于所有的 (q,a)∈∑ &#215; Q,δ (q，a)只对应一个状态。,FA”在任意时刻可以处于有穷多个状态。,FA”具有,智能,。 2633.3.2 NFA的形式定义不确定的有穷状态自动机 (non-deterministicfinite automaton,NFA)M是一个五元组M=(Q,∑,δ,q0,F)C Q,∑,q0,F的意义同 DFA。C δ,Q&#215; ∑?2Q,对?(q,a)∈ Q&#215; ∑,δ(q,a)={p1,p2,…,pm}表示 M在状态 q读入字符 a,可以选择地将状态变成 p1,或者 p2,…,或者 pm,并将读头向右移动一个带方格而指向输入字符串的下一个字符 。 2643.3.2 NFA的形式定义FA的状态转移图,FA的状态对应的等价类、FA的即时描述对 NFA都有效。接受 {x|x∈ {0,1}*，且 x含有子串 00或 11}的 FA对应的移动函数定义表。 2653.3.2 NFA的形式定义状态说明 状态 输入字符0 1启动状态 q0 {q0,q1} { q0,q2}q1 {q3} Φq2 Φ {q3}终止状态 q3 {q3} {q3} 2663.3.2 NFA的形式定义接受 {x|x∈ {0,1}*，且 x 的倒数第 10个字符为 1}的 FA对应的移动函数定义表。 2673.3.2 NFA的形式定义状态说明 状态 输入字符0 1启动状态 q0 {q0 } {q0,q1}q1 {q2} {q2}q2 {q3} {q3}q3 {q4} {q4}q4 {q5} {q5}q5 {q6} {q6}q6 {q7} {q7}q7 {q8} {q8}q8 {q9} { q9}q9 {q10} { q10}终止状态 q10 Φ Φ 2683.3.2 NFA的形式定义将 δ 扩充为QQ 2:? *对任意的 q∈ Q,w∈∑ *,a∈∑,定义a ) }，δ ( r∈p,使得w)，(q ∈$r|{p),(?)2(),(?)1(waqqq 2693.3.2 NFA的形式定义a)(q,a)}(q,p|{pa)}δ (r,∈p},{|{pa)}δ (r,∈pε ),(q,∈r|{p),(),(qraqaq和关于 DFA的结论一样，两值相同，也不用区分这两个符号。 2703.3.2 NFA的形式定义进一步扩充 δ 的定义域,δ,2Q&#215; ∑ *?2Q。对任意的 P?Q,w∈∑ *PqwqwP),(),( 2713.3.2 NFA的形式定义由于，对?(q,w)∈ Q&#215; ∑ *),(),()},({}{wqwqwqqq所以，不一定严格地区分 δ 的第 1个分量是一个状态还是一个含有一个元素的集合。 2723.3.2 NFA的形式定义对任意的 q∈ Q,w∈∑ *,a∈∑,δ (q,wa)=δ (δ (q,w),a)对输入字符串 a1a2… anδ (q,a1a2… an)=δ ((… δ (δ (q,a1),a2),… ),an) 。 2733.3.2 NFA的形式定义M接受 (识别 )的语言C 对于?x∈∑ *,如果 δ (q0,w) ∩ F≠ Φ，则称 x被 M接受,如果 δ (q0,w)∩ F=Φ，则称 M不接受 x。CL(M)={x| x∈∑ *且 δ (q0,w) ∩ F≠ Φ }，称为由 M接受 (识别 )的语言 。 2743.3.3 NFA与 DFA等价对于一个输入字符,NFA与 DFA的差异是前者可以进入若干个状态，而后者只能进入一个惟一的状态。虽然从 DFA看待问题的角度来说,NFA在某一时刻同时进入若干个状态，但是，这若干个状态合在一起的,总效果,相当于它处于这些状态对应的一个,综合状态,。因此，我们考虑让DFA用一个状态去对应 NFA的一组状态。 2753.3.3 NFA与 DFA等价NFA M1=(Q,∑,δ 1,q0,F1)与 DFAM2=(Q2,∑,δ 2,q0′,F2)的对应关系：C NFA从开始状态 q0启动，我们就让相应的 DFA从状态 [q0]启动。所以 q0′ =[ q0]。C 对于 NFA 的一个状态组 {q1,q2,…,qn}，如果 NFA在此状态组时读入字符 a后可以进入状态组 {p1,p2,…,pm},则让相应的 DFA在状态[q1,q2,…,qn]读入字符 a时，进入状态 [p1，p2,…,pm]。 2763.3.3 NFA与 DFA等价定理 3-1 NFA与 DFA等价。证明：(1)构造与 M1等价的 DFA M2 。M1=(Q,∑,δ 1,q0,F1)M2=(Q2,∑,δ 2,[q0],F2)Q2=2QF2={[p1,p2,…,pm]|{p1,p2,…,pm}?Q&{p1，p2,…,pm}∩ F1≠ Φ } 2773.3.3 NFA与 DFA等价δ 2([q1,q2,…,qn],a)=[p1,p2,…,pm]δ 1({q1,q2,…,qn},a)= {p1,p2,…,pm}(2) 证明 δ 1(q0,x)= {p1,p2,…,pm}δ 2([q0],x)=[p1,p2,…,pm]。设 x∈∑ *，施归纳于 |x|x=ε,δ 1(q0,ε )= {q0},δ 2([q0],ε )=[q0] 2783.3.3 NFA与 DFA等价设当 |x|=n是结论成立。下面证明当 |x|=n+1是结论也成立。不妨设 x=wa,|w|=n,a∈∑δ1(q0,wa)=δ1(δ1(q0,w),a)=δ1({q1,q2,…,qn},a)={p1,p2,…,pm}由归纳假设,δ 1(q0,w)={q1,q2,…,qn}?δ 2([q0]，w)=[q1,q2,…,qn] 2793.3.3 NFA与 DFA等价根据 δ 2的定义，δ 2([q1,q2,…,qn],a)=[p1,p2,…,pm]δ 1({q1,q2,…,qn},a)={p1,p2,…,pm}所以,δ 2([q0],wa)=δ 2(δ 2([q0],w),a)=δ 2([q1,q2,…,qn],a)=[p1,p2,…,pm] 2803.3.3 NFA与 DFA等价故,如果 δ 1(q0,wa)= {p1,p2,…,pm}则必有 δ 2([q0],wa)= [p1,p2,…,pm]。由上述推导可知,反向的推导也成立 。 这就是说,结论对 |x|=n+1也成立 。由归纳法原理，结论对?x∈∑ *成立。 2813.3.3 NFA与 DFA等价(3) 证明 L(M1)=L(M2)设 x∈ L(M1),且 δ 1(q0,x)= {p1,p2,…,pm}，从而 δ 1(q0,x)∩ F1≠ Φ,这就是说,{p1,p2,…,pm}∩ F1≠ Φ，由 F2的定义,[p1,p2,…,pm]∈ F2。 2823.3.3 NFA与 DFA等价再由 (2)知,δ 2([q0],x)=[p1,p2,…,pm]所以,x∈ L(M2)。 故 L(M1)?L(M2)。反过来推,可得 L(M2)? L(M1)。从而 L(M1)=L(M2)得证 。综上所述，定理成立。 283例 3-7 图 3-9所示的 NFA 对应的 DFA的状态转移函数如表 3-7所示。图 3-9 284表 3-7 状态转移函数状态说明 状态 输入字符0 1启动? [q0] [q0,q1] [q0,q2][q1] [q3] [Φ ][q2] [Φ ] [q3]终止 [q3] [q3] [q3][q0,q1] [q0,q1,q3] [q0,q2][q0,q2] [q0,q1] [q0,q2,q3]终止 [q0,q3] [q0,q1,q3] [q0,q2,q3][q1,q2] [q3] [q3]终止 [q1,q3] [q3] [q3]终止 [q2,q3] [q3] [q3][q0,q1,q2] [q0,q1,q3] [q0,q2,q3]终止? [q0,q1,q3] [q0,q1,q3] [q0,q2,q3]终止? [q0,q2,q3] [q0,q1,q3] [q0,q2,q3]终止 [q1,q2,q3] [q3] [q3]终止 [q0,q1,q2,q3] [q0,q1,q3] [q0,q2,q3][Φ ] [Φ ] [Φ ] 2853.3.3 NFA与 DFA等价不可达状态 (inaccessible state),不存在从 [q0]对应的顶点出发，到达该状态对应的顶点的路。我们称此状态从开始状态是不可达的。表 3-7中，所有标记,?” 的状态是从开始状态可达的，其他是不可达的 ――无用的。 2863.3.3 NFA与 DFA等价构造给定 NFA等价的 DFA策略C 先只把开始状态 [q0]填入表的状态列中，如果表中所列的状态列有未处理的，则任选一个未处理的状态 [q1,q2,…,qn]，对 ∑ 中的每个字符 a，计算 δ ([q1,q2,…,qn],a)，并填入相应的表项中，如果 δ ([q1,q2,…,qn],a)在表的状态列未出现过，则将它填入表的状态列。如此重复下去，直到表的状态列中不存在未处理的状态。 2873.3.3 NFA与 DFA等价图 3-11 图 3-9所示 NFA的等价 DFA 2883.4 带空移动的有穷状态自动机接受语言 {0n1m2k|n,m,k≥0}的 NFA 2893.4 带空移动的有穷状态自动机接受语言 {0n1m2k|n,m,k≥0}的 NFA是否可以构造成下图所示的,ε-NFA”？其构造显然比图 1-13所示的 NFA更容易。当然还希望它们是等价的。 2903.4 带空移动的有穷状态自动机带空移动的不确定的有穷状态自动机 (non-deterministic finite automaton with ε-moves,ε-NFA)M=(Q,∑,δ,q0,F),Q,∑,q0,F的意义同DFA。δ,Q&#215; (∑∪ {ε})?2Q 2913.4 带空移动的有穷状态自动机非空移动C?(q,a)∈ Q&#215; ∑Cδ(q,a)= {p1,p2,…,pm}C表示 M在状态 q读入字符 a，可以选择地将状态变成 p1,p2,… 或者 pm,并将读头向右移动一个带方格而指向输入字符串的下一个字符。 2923.4 带空移动的有穷状态自动机空移动C?q∈ QCδ(q,ε)= {p1,p2,…,pm}C表示 M在状态 q不读入任何字符，可以选择地将状态变成 p1,p2,… 或者 pm。也可以叫做 M在状态 q做一个空移动 (又可以称为 ε移动 )，并且选择地将状态变成 p1、p2,… 或者 pm。 2933.4 带空移动的有穷状态自动机进一步扩充 δ 的定义域,δ,2Q&#215; ∑ *?2Q。对任意的 P?Q,w∈∑ * 。对任意的 q∈ Q,w∈∑ *,a∈∑ 。⑴ ε -CLOSURE(q)={p|从 q到 p有一条标记为 ε 的路 }。PppC L O S U R EPC L O S U R E )()()2( 2943.4 带空移动的有穷状态自动机)(),(?)3( qC L O S U R Eq),(),()},(),(|{)(),()4(wrrararpwqrpPPC L O S U R Ewaq使得 2953.4 带空移动的有穷状态自动机进一步扩展移动函数,2 Q&#215; ∑?2Q 。对任意 (P,a)∈ 2Q&#215; ∑ 。PqaqaP),(),()5(PqwqwP),(?),(?)6( 2963.4 带空移动的有穷状态自动机在 ε -NFA中，对任意 a∈∑,q∈ Q，),(),(? aqaq需要严格区分。 297图 3-14 所示 ε -NFA状态δε 0 1 2 ε 0 1 2q0 { q1} { q0} Φ Φ {q0,q1,q2}{q0,q1,q2}{q1,q2}{q2}q1 { q2} Φ { q1} Φ {q1,q2} Φ {q1,q2}{q2}q2 Φ Φ Φ { q2} {q2} Φ Φ {q2} 2983.4 带空移动的有穷状态自动机M接受 (识别 )的语言对于?x∈∑ *,仅当Fxq?),(? 0?时，称 x被 M接受。}),(?|{)( 0* FxqxxML并且 2993.4 带空移动的有穷状态自动机定理 3-2ε -NFA与 NFA等价。证明：设有 ε -NFA M1=(Q,∑,δ 1,q0，F)(1) 构造与之等价的 NFA M2 。取 NFA M2=(Q,∑,δ 2,q0,F2)F∪ {q0} 如果 F∩ε-CLOSURE(q0)≠ΦF2=F 如果 F∩ ε -CLOSURE(q0)=Φ),(?),( 12 aqaq 3003.4 带空移动的有穷状态自动机(2) 施归纳于 |x|，证明对?x∈∑ + 。),(?),( 12 xqxqδ 2(q0,x)= δ 2(q0,wa)=δ 2(δ 2(q0,w),a)=δ 2((q0,w),a) 3013.4 带空移动的有穷状态自动机),(),(),(),,(|({)),((),(),(0101101),(1),(1),(2010101xqwaqaqpwqqpC L O S U R EaqC L O S U R Eaqaqwqqwqqwqq 3023.4 带空移动的有穷状态自动机(3) 证明,对?x∈∑ +,δ 2(q0,x) ∩ F2≠ Φ的充分必要条件是Fxq?),(?1?⑷ 证明 ε ∈ L(M1)?ε ∈ L(M2) 。 3033.4 带空移动的有穷状态自动机例 3-4 求与图 3-14所示 ε -NFA等价的 NFA。 3043.5 FA是正则语言的识别器3.5.1 FA与右线性文法DFA M=(Q,∑,δ,q0,F)，处理句子a1a2… an的特性。}