形式语言与自动机-经典教学课件(完整版)

1、2020/7/23,1,形式语言与自动机Formal Languages and Automata,2020/7/23,2,课程目的和基本要求,课程性质 技术基础 基础知识要求 数学分析（或者高等数学），离散数学 主要特点 抽象和形式化 理论证明和构造性 基本模型的建立与性质,2020/7/23,3,课程目的和基本要求,本专业人员4种基本的专业能力 计算思维能力 算法的设计与分析能力 程序设计和实现能力 计算机软硬件系统的认知、分析、设计与应用能力 计算思维能力 逻辑思维能力和抽象思维能力 构造模型对问题进行形式化描述 理解和处理形式模型,2020/7/23,4,课程目的和基本要求,知识 掌握

2、正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。 能力 培养学生的形式化描述和抽象思维能力。 使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。,2020/7/23,5,主要内容,语言的文法描述。 RL RG、 FA、RE、RL的性质 。 CFL CFG(CNF、GNF)、PDA、CFL的性质。 TM 基本TM、构造技术、TM的修改。 CSL CSG、LBA。,2020/7/23,6,教材及主要参考书目,蒋宗礼，姜守旭. 形式语言与自动机理论. 北京：清华大学出版社，2003年 John E Hopcroft, Rajeev Mo

3、twani, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation (2nd Edition). Addison-Wesley Publishing Company, 2001 John E Hopcroft, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, 1979,2020/7/23,7,第1章 绪论,1.1 集

4、合的基础知识 1.1.1 集合及其表示 集合：一定范围内的、确定的、并且彼此可以区分的对象汇集在一起形成的整体叫做集合(set)，简称为集(set)。 元素：集合的成员为该集合的元素(element)。 集合描述形式。 基数。 集合的分类。,2020/7/23,8,1.1.2 集合之间的关系,子集 如果集合A中的每个元素都是集合B的元素，则称集合A是集合B的子集(subset)，集合B是集合A的包集(container)。记作AB。也可记作BA。AB读作集合A包含在集合B中；BA读作集合B包含集合A。 如果AB，且xB，但xA，则称A是B的真子集(proper subset)，记作AB,202

5、0/7/23,9,1.1.2 集合之间的关系,集合相等 如果集合A，B含有的元素完全相同，则称集合A与集合B相等(equivalence)，记作A=B。 对任意集合A、B、C： A=B iff AB且BA。 如果AB，则|A|B|。 如果AB，则|A|B|。 如果A是有穷集，且AB，则|B|A|。,2020/7/23,10,1.1.2 集合之间的关系, 如果AB，则对xA，有xB。 如果AB，则对xA，有xB并且xB，但xA。 如果AB且BC，则AC。 如果AB且BC，或者AB且BC，或者AB且BC，则AC。 如果A=B，则|A|=|B|。,2020/7/23,11,1.1.3 集合的运算,并

6、(union) A与B的并(union)是一个集合，该集合中的元素要么是A的元素，要么是B的元素，记作AB。 AB=a|aA或者aB A1A2An=a|i，1in，使得aAi A1A2An =a|i，iN,使得aAi,2020/7/23,12,交(intersection),集合A和B中都有的所有元素放在一起构成的集合为A与B的交 ，记作AB。 AB=a|aA且aB “”为交运算符，AB读作A交B。 如果AB=，则称A与B不相交。 AB= BA。 (AB)C=A(BC)。 AA=A。,2020/7/23,13,交(intersection), AB=A iff AB。 A=。 |AB|min|

7、A|，|B|。 A(BC)=(AB)(AC)。 A(BC)=(AB)(AC)。 A(AB)=A。 A(AB)=A。,2020/7/23,14,差(difference),属于A，但不属于B的所有元素组成的集合叫做A与B的差，记作A-B。 A-B=a|aA且aB “-”为减(差)运算符，A-B读作A减B。 A-A=。 A-=A。 A-B B-A。 A-B=A iff AB=。 A(B-C)=(AB)-(AC)。 |A-B|A|。,2020/7/23,15,对称差(symmetric difference),属于A但不属于B，属于B但不属于A的所有元素组成的集合叫A与B的对称差，记作AB。 AB=

8、a|aA且aB或者aA且aB “”为对称差运算符。AB读作A对称减B。 AB=(AB)-(AB)=(A-B)(B-A)。,2020/7/23,16,笛卡儿积(Cartesian product),A与B的笛卡儿积(Cartesian product)是一个集合，该集合是由所有这样的有序对(a，b)组成的：其中aA，bB ，记作AB。 AB=(a，b)|aA 对qQ2，a，(q，a)=2(q，a)； (f1，)=f； (f2，)=f。,2020/7/23,374,4.3.1 RE到FA的等价变换,n=k+1,r=r1+r2,2020/7/23,375,4.3.1 RE到FA的等价变换,M=(Q1

9、Q2，q01，f2) 对qQ1-f1，a (q，a)=1(q，a)； 对qQ2-f2，a (q，a)=2(q，a)； (f1，)=q02,2020/7/23,376,4.3.1 RE到FA的等价变换,r=r1r2,2020/7/23,377,4.3.1 RE到FA的等价变换,M=(Q1q0，f，q0，f) 其中q0，fQ1，定义为 对qQ1-f1，a，(q，a)=1(q，a)。 (f1，)=q01，f。 (q0，)=q01，f。,2020/7/23,378,4.3.1 RE到FA的等价变换,r=r1*,2020/7/23,379,4.3.1 RE到FA的等价变换,按照定理4-1证明给出的方法构

10、造一个给定RE的等价FA时，该FA有可能含有许多的空移动。 可以按照自己对给定RE的“理解”以及对FA的 “理解” “直接地”构造出一个比较“简单”的FA。 定理证明中所给的方法是机械的。由于“直接地”构造出的FA的正确性依赖于构造者的“理解”，所以它的正确性缺乏有力的保证。,2020/7/23,380,4.3.1 RE到FA的等价变换,例 4-3 构造与 (0+1)*0+(00)*等价的FA。,2020/7/23,381,4.3.1 RE到FA的等价变换,按照对(0+1)*0+(00)*的“理解” “直接地”构造出的FA。,2020/7/23,382,4.3.2 RL可以用RE表示,计算DF

11、A的每个状态对应的集合字母表的克林闭包的等价分类，是具有启发意义的。 这个计算过程难以“机械”地进行。 计算q1到q2的一类串的集合：Rkij 。 图上作业法。,2020/7/23,383,4.3.2 RL可以用RE表示,定理4-2 RL可以用RE表示。 设DFA M=(q1，q2，qn，q1，F) Rkij=x|(qi，x)=qj而且对于x的任意前缀y(yx，y)，如果(qi，y)=ql，则lk。,2020/7/23,384,4.3.2 RL可以用RE表示,R0ij=,a|(qi，a)=qj如果ij,a|(qi，a)=qj如果i=j,Rkij= Rk-1ik( Rk-1kk)* Rk-1kj

12、 Rk-1ij,2020/7/23,385,4.3.2 RL可以用RE表示,图上作业法 启示,2020/7/23,386,4.3.2 RL可以用RE表示,图上作业法操作步骤 预处理： 用标记为X和Y的状态将M“括起来”： 在状态转移图中增加标记为X和Y的状态，从标记为X的状态到标记为q0的状态引一条标记为的弧；从标记为q(qF)的状态到标记为Y的状态分别引一条标记为的弧。 去掉所有的不可达状态。,2020/7/23,387,4.3.2 RL可以用RE表示, 对通过步骤(1)处理所得到的状态转移图重复如下操作，直到该图中不再包含除了标记为X和Y外的其他状态，并且这两个状态之间最多只有一条弧。 并

13、弧 将从q到p的标记为r1，r2，rg并行弧用从q到p的、标记为r1+r2+rg的弧取代这g个并行弧。,2020/7/23,388,4.3.2 RL可以用RE表示,去状态1 如果从q到p有一条标记为r1的弧，从p到t有一条标记为r2的弧，不存在从状态p到状态p的弧，将状态p和与之关联的这两条弧去掉，用一条从q到t的标记为r1r2的弧代替。 去状态2 如果从q到p有一条标记为r1的弧，从p到t有一条标记为r2的弧，从状态p到状态p标记为r3的弧，将状态p和与之关联的这三条弧去掉，用一条从q到t的标记为r1r3*r2的弧代替。,2020/7/23,389,4.3.2 RL可以用RE表示,去状态3

14、如果图中只有三个状态，而且不存在从标记为X的状态到达标记为Y的状态的路，则将除标记为X的状态和标记为Y的状态之外的第3个状态及其相关的弧全部删除。,2020/7/23,390,4.3.2 RL可以用RE表示, 从标记为X的状态到标记为Y的状态的弧的标记为所求的正则表达式。如果此弧不存在，则所求的正则表达式为。,2020/7/23,391,4.3.2 RL可以用RE表示,例 4-4 求图4-14所示的DFA等价的RE 。,2020/7/23,392,4.3.2 RL可以用RE表示,预处理。,2020/7/23,393,4.3.2 RL可以用RE表示,去掉状态q3。,2020/7/23,394,4

15、.3.2 RL可以用RE表示,去掉状态q4。,2020/7/23,395,4.3.2 RL可以用RE表示,合并从标记为q2的状态到标记为Y的状态的两条并行弧。,2020/7/23,396,4.3.2 RL可以用RE表示,去掉状态q0。,2020/7/23,397,4.3.2 RL可以用RE表示,并弧。,2020/7/23,398,4.3.2 RL可以用RE表示,去掉状态q1。,2020/7/23,399,4.3.2 RL可以用RE表示,去掉状态q2。,1*0(11*0)*0(00*111*0+00*10+11*0)(11*0)*0)(00*+00*1)就是所求。,2020/7/23,400,4

16、.3.2 RL可以用RE表示,几点值得注意的问题 如果去状态的顺序不一样，则得到的RE可能在形式是不一样，但它们都是等价的。 当DFA的终止状态都是不可达的时候，状态转移图中必不存在从开始状态到终止状态的路。此时，相应的RE为。 不计算自身到自身的弧，如果状态q的入度为n，出度为m，则将状态q及其相关的弧去掉之后，需要添加n*m条新弧。,2020/7/23,401,4.3.2 RL可以用RE表示, 对操作的步数施归纳，可以证明它的正确性。 推论4-1 正则表达式与FA、正则文法等价，是正则语言的表示模型。,2020/7/23,402,4.4 正则语言等价模型的总结,2020/7/23,403,

17、4.5 小结,本章讨论了RL及其与FA的等价性。 字母表上的RE用来表示上的RL。、a（a），是上的最基本的RE，它们分别表示语言、a，以此为基础，如果r和s分别是上的表示语言R和S的RE，则r+s、rs 、r*分别是上的表示语言RS、RS、 R*的RE。如果L(r)=L(s)，则称r与s等价。,2020/7/23,404,4.5 小结, RE对乘、加满足结合律；乘对加满足左、右分配律；加满足交换率和幂等率；是加运算的零元素；是乘运算的单位元；是乘运算的零元素。 RE是RL的一种描述。容易根据RE构造出与它等价的FA。反过来，可以用图上作业法构造出与给定的DFA等价的RE。 RL的5种等价描述

18、模型转换图。,2020/7/23,405,第5章 RL的性质,RL性质 泵引理及其应用 并、乘积、闭包、补、交 正则代换、同态、逆同态的封闭性 从RL固有特征寻求表示的一致性 Myhill-Nerode定理 FA的极小化 RL的几个判定问题 空否、有穷否、两个DFA等价否、成员关系,2020/7/23,406,5.1 RL的泵引理,泵引理(pumping lemma) 设L为一个 RL ，则存在仅依赖于L的正整数N，对于zL，如果|z|N，则存在u、v、w，满足 z=uvw； |uv|N； |v|1； 对于任意的整数i0，uviwL； N不大于接受L的最小DFA M的状态数。,2020/7/2

19、3,407,5.1 RL的泵引理,证明思想,2020/7/23,408,5.1 RL的泵引理,证明： DFA在处理一个足够长的句子的过程中，必定会重复地经过某一个状态。换句话说，在DFA的状态转移图中，必定存在一条含有回路的从启动状态到某个终止状态的路。由于是回路，所以，DFA可以根据实际需要沿着这个回路循环运行，相当于这个回路中弧上的标记构成的非空子串可以重复任意多次。,2020/7/23,409,5.1 RL的泵引理,M=(Q，q0，F) |Q|=N z= a1a2ammN (q0，a1a2ah)=qh 状态序列q0，q1，qN中，至少有两个状态是相同：qk=qj,2020/7/23,41

20、0,5.1 RL的泵引理,(q0，a1a2ak)=qk (qk，ak+1aj)=qj=qk (qj，aj+1am)=qm 对于任意的整数i0 (qk，(ak+1aj)i) =(qk，(ak+1aj)i-1) =(qk，ak+1aj)=qk,2020/7/23,411,5.1 RL的泵引理,故， (q0，a1a2ak(ak+1aj)i aj+1am)=qm 也就是说， a1a2ak(ak+1aj)i aj+1amL(M) u= a1a2ak， v=ak+1aj， w= aj+1am uviwL,2020/7/23,412,5.1 RL的泵引理,例 5-1 证明0n1n|n1不是 RL。 证明：

21、假设L=0n1n|n1 是 RL z=0N1N 按照泵引理所述 v=0kk1 此时有， u=0N-k-j w=0j1N,2020/7/23,413,5.1 RL的泵引理,从而有， uviw=0N-k-j(0k)i0j1N=0N+(i-1)k1N 当i=2时，我们有： uv2w=0N+(2-1)k1N = 0N+k1N 注意到k1，所以， N+kN。 这就是说， 0N+k1NL 这与泵引理矛盾。所以，L不是 RL。,2020/7/23,414,5.1 RL的泵引理,例 5-2 证明0n|n为素数不是 RL。 证明：假设L=0n|n为素数 是 RL。 取 z=0N+p L ， 不妨设v=0k，k1

22、 从而有， uviw=0N+p-k-j(0k)i0j =0N+p+(i-1)k,2020/7/23,415,5.1 RL的泵引理,当i=N+p+1时， N+p+(i-1)k=N+p+(N+p+1-1)k = N+p+(N+p)k = (N+p)(1+k) 注意到k1，所以 N+p+(N+p+1-1)k=(N+p)(1+k) 不是素数。故当i=N+p+1时， uvN+p+1w=0(N+p)(1+k) L 这与泵引理矛盾。所以，L不是 RL。,2020/7/23,416,5.1 RL的泵引理,例 5-3 证明0n1m2n+m|m，n1不是 RL。 证明：假设L=0n1m2n+m|m，n1 是 RL

23、。 取z=0N1N22N 设v=0k k1 从而有， uviw=0N-k-j(0k)i0j1N22N =0N+(i-1)k1N22N,2020/7/23,417,5.1 RL的泵引理,uv0w=0N+(0-1)k1N22N = 0N-k1N22N 注意到k1， N-k+N=2N-k2N 0N-k1N22N L 这个结论与泵引理矛盾。所以，L不是 RL。,2020/7/23,418,5.1 RL的泵引理,用来证明一个语言不是 RL 不能用泵引理去证明一个语言是 RL。 由于泵引理给出的是 RL 的必要条件，所以，在用它证明一个语言不是 RL 时，我们使用反证法。 泵引理说的是对 RL 都成立的条

24、件，而我们是要用它证明给定语言不是 RL ，这就是说，相应语言的“仅仅依赖于L的正整数N”实际上是不存在的。所以，我们一定是无法给出一个具体的数的。因此，人们往往就用符号N来表示这个“假定存在”、而实际并不存在的数。,2020/7/23,419,5.1 RL的泵引理, 由于泵引理指出，如果L是 RL ，则对任意的zL，只要|z|N，一定会存在u、v、w，使uviwL对所有的i成立。因此，我们在选择z时，就需要注意到论证时的简洁和方便。 当一个特意被选来用作“发现矛盾”的z确定以后，就必须依照|uv|N和|v|1的要求，说明v不存在(对“存在u、v、w”的否定) 。,2020/7/23,420,

25、5.1 RL的泵引理, 与选z时类似，在寻找i时，我们也仅需要找到一个表明矛盾的“具体”值就可以了(对“所有i”的否定)。 一般地，在证明一个语言不是 RL 的时候，我们并不使用泵引理的第(5)条。 事实上，引理所要求的|uv|N并不是必须的。这个限制为我们简化相应的证明提供了良好支撑扩充了的泵引理 。,2020/7/23,421,5.2 RL的封闭性,封闭性(closure property) 如果任意的、属于同一语言类的语言在某一特定运算下所得的结果仍然是该类语言，则称该语言类对此运算是封闭的 有效封闭性(valid closure property) 给定一个语言类的若干个语言的描述，如

26、果存在一个算法，它可以构造出这些语言在给定运算下所获得的运算结果的相应形式的语言描述，则称此语言类对相应的运算是有效封闭的。,2020/7/23,422,5.2 RL的封闭性,定理 5-1 RL 在并、乘积、闭包运算下是封闭的。 根据RE的定义，立即可以得到此定理。,2020/7/23,423,5.2 RL的封闭性,定理 5-2 RL 在补运算下是封闭的。 证明： M=(Q，q0，F) L(M)=L， 取DFA M= (Q，q0，Q-F) 显然，对于任意的x*， (q0，x)=fF (q0，x)=fQ-F 即： xL(M) xL(M)， L(M)= *-L(M)。 所以， RL 在补运算下是封

27、闭的。定理得到证明。,2020/7/23,424,5.2 RL的封闭性,定理 5-3 RL 在交运算下封闭。 证明思路,2020/7/23,425,5.2 RL的封闭性,正则代换(regular substitution) 设、是两个字母表，映射,被称为是从到的代换。如果对于a，f(a)是上的 RL ，则称f为正则代换。,2020/7/23,426,5.2 RL的封闭性,先将f的定义域扩展到*上：, f()=； f(xa)=f(x)f(a)。,2020/7/23,427,5.2 RL的封闭性,再将f的定义域扩展到,对于L*,2020/7/23,428,5.2 RL的封闭性,例 5-4 设=0，

28、1，=a，b，f(0)=a，f(1)=b*，则 f(010)=f(0)f(1)f(0)=ab*a f(11，00)=f(11)f(00) =f(1)f(1)f(0)f(0)=b*b*+aa=b*+aa f(L(0*(0+1)1*)=L(a*(a+b*)(b*)*) =L(a*(a+b*)b*)=L(a*ab*+a*b*b*) =L(a*b*),2020/7/23,429,5.2 RL的封闭性,f是正则代换,则 f()=； f()=； 对于a，f(a)是上的RE； 如果r，s是上的RE，则 f(r+s)=f(r)+f(s) f(rs)=f(r)f(s) f(r*)=f(r)* 是上的RE。,20

29、20/7/23,430,5.2 RL的封闭性,定理 5-4 设L是上的一个 RL,是正则代换，则f(L)也是 RL。 证明： 描述工具：RE。 对r中运算符的个数n施以归纳，证明f(r)是表示f(L)的RE。,2020/7/23,431,5.2 RL的封闭性,当n=0时，结论成立。 当nk时定理成立,即当r中运算符的个数不大于k时：f(L(r) = L(f。 当n=k+1时，,2020/7/23,432,5.2 RL的封闭性, r=r1+r2。 f(L)=f(L(r) =f(L(r1+r2) =f(L(r1)L(r2)RE的定义 =f(L(r1)f(L(r2)正则代换的定义 =L(f(r1)L

30、 (f (r2)归纳假设 =L(f(r1)+f (r2)RE的定义 =L(f(r1+r2)RE的正则代换的定义 =L(f(r),2020/7/23,433,5.2 RL的封闭性, r=r1r2。 f(L)=f(L(r) =f(L(r1r2) =f(L(r1) L(r2)RE的定义 =f(L(r1) f(L(r2)正则代换的定义 =L(f(r1) L (f (r2)归纳假设 =L(f(r1) f (r2)RE的定义 =L(f(r1r2)RE的正则代换的定义 =L(f(r),2020/7/23,434,5.2 RL的封闭性, r=r1*。 f(L)=f(L(r) =f(L(r1*) =f(L(r1

31、)*)RE的定义 =(f(L(r1)*正则代换的定义 =(L(f(r1)*归纳假设 =L(f(r1)*)RE的定义 =L(f(r1*)RE的正则代换的定义 =L(f(r),2020/7/23,435,5.2 RL的封闭性,例5-5 设=0，1，2，=a，b，正则代换f定义为： f(0)=ab； f(1)=b*a*； f(2)=a*(a+b) 则： f(00)=abab； f(010)=abb*a*ab=ab+a+b；,2020/7/23,436,5.2 RL的封闭性, f(0+1+2)*)=(ab+b*a*+ a*(a+b)* =(b*a*+a*(a+b)*=(a+b)*； f(0(0+1+2

32、)*)=ab(ab+b*a*+ a*(a+b)* =ab(a+b)*； f(012)=abb*a* a* (a+b)= ab+a*(a+b)； f(0+1)*)=(ab+ b*a* )* =(ab+b+a+ b*a* )*=(a+b)* 。,2020/7/23,437,5.2 RL的封闭性,同态映射(homomorphism) 设、是两个字母表，,f为映射，如果对于x，y*， f(xy)=f(x)f(y)， 则称f为从到*的同态映射。,2020/7/23,438,5.2 RL的封闭性,对于L*，L的同态像,对于w*，w的同态原像是一个集合,对于L*，L的同态原像是一个集合,2020/7/23,

33、439,5.2 RL的封闭性,例5-6 设=0，1，=a，b，同态映射f定义为 f(0)=aa f(1)=aba 则： f(01)=aaaba； f(01)*)=(aaaba)*； f -1(aab)=；,2020/7/23,440,5.2 RL的封闭性, f -1(aa)=0； f -1(aaa，aba，abaaaaa，abaaaaaa) =1，100； f -1(ab+ba)*a)=1； f(f -1(ab+ba)*a)=f(1)=aba。 令L=(ab+ba)*a，上述(7)表明，f(f -1(L) L f(f -1(L) L,2020/7/23,441,5.2 RL的封闭性,推论5-1

34、 RL 的同态像是 RL。 证明： 注意到同态映射是正则代换的特例，可以直接的到此结论。 该定理表明， RL 在同态映射下是封闭的。,2020/7/23,442,5.2 RL的封闭性,定理 5-5 RL 的同态原像是 RL 。 证明： 使用DFA作为描述工具。 (1) 接受RL的同态原像的FA的构造思想。 让新构造出的FA M用一个移动去模拟M处理f(a)所用的一系列移动。 对于中的任意字符a，如果M从状态q开始处理f(a)，并且当它处理完f(a)时到达状态p，则让M在状态q读入a时，将状态变成p。,2020/7/23,443,5.2 RL的封闭性,M具有与M相同的状态，并且，在M对应的状态转

35、移图中，从状态q到状态p有一条标记为a的弧当且仅当在M的状态转移图中，有一条从状态q到状态p的标记为f(a)的路。 (2) 接受RL的同态原像的FA的形式描述。 设DFA M=(Q，q0，F)，L(M)=L， 取DFA M=(Q，q0，F) (q，a)= (q，f(a),2020/7/23,444,5.2 RL的封闭性,(3) 等价证明。 施归纳于|x|，证明对于x*， (q0，x)=(q0，f(x) 当|x|=0时，结论显然成立。 设当|x|=k是结论成立，往证当|x|=k+1时结论成立。 不妨设x=ya，其中|y|=k,2020/7/23,445,5.2 RL的封闭性,(q0，x)=(q0

36、，ya) =(q0，y)，a) =( (q0，f(y)，a)归纳假设 =(q0，f(y)，f(a)的定义 =(q0，f(y)f(a)的意义 =(q0，f(ya)同态映射性质 =(q0，f(x),2020/7/23,446,5.2 RL的封闭性,这表明，结论对|x|=k+1成立。由归纳法原理，结论对x*成立。 x*， (q0，x)F (q0，f(x) F。 由于对x*，(q0，x)=(q0，f(x)， 所以， (q0，x)F (q0，f(x)F。 故 L(M)=f-1(L(M) 定理得证。,2020/7/23,447,5.2 RL的封闭性,商(quotient) 设L1、L2*，L2除以L1的商

37、定义为： L1/L2=x|yL2使得xyL1。 计算语言的商主要是考虑语言句子的后缀。只有当L1的句子的后缀在L2 中时，其相应的前缀才属于L1/L2。所以，当L2时， L1 L1/L2。,2020/7/23,448,5.2 RL的封闭性,注意以下有意思的情况： 取L1=000，L2=，L3=，0 L4=，0，00，L5=，0，00，000 L1/L2=000= L1 L1/L3=000，00 L1/L4=000，00，0 L1/L5=000，00，0，,2020/7/23,449,5.2 RL的封闭性,定理5-6 L1、L2*，如果L1是 RL ，则L1/L2也是 RL 。 证明：设L1 *

38、，是 RL ， DFA M=(Q，q0，F)，L(M)=L1 DFA M=(Q，q0，F) F=q|yL2，(q，y)F 显然， L(M)= L1/L2。 定理得证。,2020/7/23,450,5.3 Myhill-Nerode 定理与DFA的极小化,对给定 RL L，DFA M接受L，M不同，由RM确定的*上的等价类也可能不同。 如果M是最小DFA，则M所给出的等价类的个数应该是最少的。 最小DFA是不是惟一的？如果是，如何构造？ 最小DFA的状态对应的集合与其他DFA的状态对应的集合有什么样的关系，用这种关系是否能从一般的DFA出发，求出最小DFA？,2020/7/23,451,5.3.

39、1 Myhill-Nerode 定理,DFA M确定的等价关系。 M=(Q，q0，F)，对于x，y* x RM y (q0，x)=(q0，y)。 显然， x RM y qQ，x，yset(q),2020/7/23,452,5.3.1 Myhill-Nerode 定理,例 5-8 设 L=0*10*，它对应的DFA M如下图。,2020/7/23,453,5.3.1 Myhill-Nerode 定理,对应于q0：(00)n RM (00)mn，m0； 对应于q1：0(00)n RM 0(00)mn，m0； 对应于q2：(00)n1 RM (00)m1n，m0； 对应于q3：0(00)n 1RM

40、0(00)m1n，m0； 对应于q4：0(00)n 10kRM 0(00)m10hn，m0,k,h1； (00)n10k RM (00)m10hn,m0，k,h1； 0(00)n 10kRM (00)m10hn,m0，k,h1； 也就是： 0n 10kRM 0m10hn,m0，k,h1； 对应于q5：x RM yx，y为至少含两个1的串。,2020/7/23,454,5.3.1 Myhill-Nerode 定理,L确定的*上的关系RL。 对于x，y*， x RL y (对z*，xzL zyL) 对于x，y*，如果x RL y，则在x和y后无论接*中的任何串z，xz和yz要么都是L的句子，要么都

41、不是L的句子。,2020/7/23,455,5.3.1 Myhill-Nerode 定理,任意x，yset(q)，(q0，x)=(q0，y)=q 对于z*， (q0，xz)=(q0，x)，z) =(q，z) =(q0，y) ，z) =(q0，yz) 这就是说， (q0，xz)F (q0，yz)F,2020/7/23,456,5.3.1 Myhill-Nerode 定理,即，对于z*， xzL yzL。 表明， x RL y， 也就是 x RL(M)y。,2020/7/23,457,5.3.1 Myhill-Nerode 定理,右不变的(right lnvariant)等价关系 设R是*上的等价

42、关系，对于x，y*，如果x RL y，则必有xz RL yz对于z*成立，则称R是右不变的等价关系。,2020/7/23,458,5.3.1 Myhill-Nerode 定理,命题 5-1 对于任意DFA M=(Q，q0，F)，M所确定的*上的关系RM为右不变的等价关系。 证明： RM是等价关系。 自反性显然 。 对称性：x，y*， x RM y (q0，x)=(q0，y)根据RM的定义； (q0，y)=(q0，z)“=”的对称性； y RM x根据RM的定义。,2020/7/23,459,5.3.1 Myhill-Nerode 定理,传递性：设x RM y，y RM z。 由于x RM y，

43、(q0，x)=(q0，y) 由于y RM z，(q0，y)=(q0，z) 由“=”的传递性知， (q0，x)=(q0，z) 再由RM的定义得： x RM z 即RM是等价关系。,2020/7/23,460,5.3.1 Myhill-Nerode 定理, RM 是右不变的 设x RM y。则(q0，x)=(q0，y)=q 所以，对于z*， (q0，xz)=(q0，x)，z) =(q，z) =(q0，y) ，z) =(q0，yz) 这就是说，(q0，xz)=(q0，yz)，再由RM的定义， xz RM yz 所以，RM 是右不变的等价关系。,2020/7/23,461,5.3.1 Myhill-N

44、erode 定理,命题 5-2 对于任意L*，L所确定的*上的关系RL为右不变的等价关系 。 证明： RL是等价关系。 自反性显然。 对称性：不难看出：x RL y (对z*，xzL yzL) y RL x,2020/7/23,462,5.3.1 Myhill-Nerode 定理,传递性：设x RL y，y RL z。 x RL y (对w*，xwL ywL) y RL z (对w*，ywL zwL) 所以， (w*,xwL ywL 且ywL zwL) 即： (对w*，xwL zwL) 故： x RL z 即RL是等价关系。,2020/7/23,463,5.3.1 Myhill-Nerode

45、定理, RL 是右不变的。 设x RL y。由RL的定义，对w，v*，xwvL zwvL，注意到v的任意性，知， xw RL yw。 所以，RL是右不变的等价关系。,2020/7/23,464,5.3.1 Myhill-Nerode 定理,指数(index) 设R是*上的等价关系，则称|*/R|是R关于*的指数。简称为R的指数。简称*的关于R的一个等价类，也就是*/R的任意一个元素，为R的一个等价类,2020/7/23,465,5.3.1 Myhill-Nerode 定理,例 5-9 图5-4 所给DFA M所确定的RM的指数为6。RM将*分成6个等价类： set(q0)=(00)n | n0

46、； set(q1)=0(00)n | n0； set(q2)=(00)n1 | n，m0； set(q3)=0(00)n 1|n0； set(q4)=0n 10k|n0，k1； set(q5)=x|x为至少含两个1的串。,2020/7/23,466,5.3.1 Myhill-Nerode 定理,RM是RL(M)的“加细”(refinement) x，y*，如果x RM y，必有x RL(M) y成立。即对于任意DFA M=(Q,q0,F)。 |*/RL(M)|*/RM|Q| 按照RM中被分在同一等价类的串，在按照RL(M)分类时，一定会被分在同一个等价类。 RM对*的划分比RL(M)对*的划分

47、更“细”。称RM是RL(M)的“加细”(refinement)。,2020/7/23,467,5.3.1 Myhill-Nerode 定理,*/RM =set(q0)，set(q1)，set(q2)，set(q3)，set(q4)，set(q5) 取00set(q0)，000set(q1)。 对于任意的x*，当x含且只含一个1时，00 xL(M)，000 xL(M)；当x不含1或者含多个1时，00 xL(M)，000 xL(M)。这就是说，对于任意的x*，00 xL(M) 000 xL(M)。即按照RL(M)，00与000被分在同一个等价类中。从而set(q0)和set(q1) 被包含在RL(

48、M)的同一个等价类中。,2020/7/23,468,5.3.1 Myhill-Nerode 定理, 取00set(q0)，001set(q2)。 取特殊的字符串1*，001L(M)，但0011L(M)。所以，根据RL(M)，set(q0)和set(q2)不能被“合并”到一个等价类中。 类似地，根据RL(M)，set(q3)、set(q4)、set(q5)也都不能被“合并”到set(q0)的句子所在的等价类中。,2020/7/23,469,5.3.1 Myhill-Nerode 定理, 取001set(q2)，01set(q3)。 对于任意的x*，x要么不含1，要么含有1。当x不含1时，001x

49、L(M)，01xL(M)；当x含有1时，001xL(M)，01xL(M)。这就是说，对于任意的x*，001xL(M) 01xL(M)。即按照RL(M)，001与01属于RL(M)的同一个等价类中。从而set(q2)和set(q3) 被包含在RL(M)的同一个等价类中。,2020/7/23,470,5.3.1 Myhill-Nerode 定理, 取1set(q2)， 10set(q4)。 对于任意的x*，x要么不含1，要么含有1。当x不含1时，1xL(M)，10 xL(M)；当x含有1时，1xL(M)，10 xL(M)。这就是说，对于任意的x*，1xL(M) 10 xL(M)。即按照RL(M)，

50、1与10被分在RL(M)的同一个等价类中。从而在set(q2)和set(q4)被包含在RL(M)的同一个等价类中。,2020/7/23,471,5.3.1 Myhill-Nerode 定理, 取1set(q2)， 11set(q5)。 注意到1=1，11=11；而1L(M)，11L(M)。即1和11不满足关系RL(M)，所以，set(q2)和set(q5)不能被“合并”到RL(M)的同一个等价类中。在这里，*是一个特殊的字符串。,2020/7/23,472,5.3.1 Myhill-Nerode 定理,*/RL(M)= set(q0)set(q1)，set(q2)set(q3)set(q4)，

51、set(q5) 不含1：0= set(q0)set(q1)=0*； 含一个1：1= set(q2)set(q3)set(q4)=0*10*； 含多个1：11= set(q5)=0*10*1(0+1)* 。,2020/7/23,473,5.3.1 Myhill-Nerode 定理,定理5-1 (Myhill-Nerode定理)如下三个命题等价： L*是 RL ； L是*上的某一个具有有穷指数的右不变等价关系R的某些等价类的并； RL具有有穷指数。,2020/7/23,474,5.3.1 Myhill-Nerode 定理,证明： 由(1)可以推出(2) 设L*是 RL ，所以，存在DFA M=(Q

52、，q0，F)，使得L(M)=L。由命题5-3-1，RM是*上的右不变等价关系，而且|*/RM|Q|，所以，RM具有有穷指数。而,L是*上的具有有穷指数的右不变等价关系RM的、对应于M的终止状态的等价类的并。,2020/7/23,475,5.3.1 Myhill-Nerode 定理,由(2)可以推出(3)。 设x R y，由R的右不变性可知，对于任意z*， xz R yz 而L是R的某些等价类的并，所以， xzL yzL 根据RL的定义， x RL y 故R是RL的加细。由于R具有有穷指数，所以，RL具有有穷指。,2020/7/23,476,5.3.1 Myhill-Nerode 定理,由(3)

53、可以推出(1)。 令M=(*/RL,x|xL) 表示所在的等价类对应的状态； x 表示x所在的等价类对应的状态。 对于(x,a)(*/RL),(x,a)=xa 定义的相容性 L(M)=L,2020/7/23,477,5.3.1 Myhill-Nerode 定理,例5-10 用定理5-7证明0n1n|n0不是 RL 根据L的句子的特征来寻找RL的等价类。 L的句子的主要特点有两个： 句子中所含的字符0的个数与所含的字符1的个数相同。 所有的0都在所有的1的前面 可以得到如下一些等价类。,2020/7/23,478,5.3.1 Myhill-Nerode 定理,10=x|x=0n1m(mn+1)或

54、者x中含子串10 所在的等价类； 10所在的等价类； 200所在的等价类； 3000所在的等价类； n0n所在的等价类； 所以，RL的指数是无穷的。因此，L不是 RL。,2020/7/23,479,5.3.1 Myhill-Nerode 定理,推论 5-1 对于任意的 RL L，如果DFA M=(Q，q0，F)满足L(M)=L，则|*/RL|Q|。 表明，对于任意DFA M=(Q，q0，F)，|Q|*/RL(M)|。 也表明，对任意一个 RL L，按照定理中所给的方法构造出来的DFA M是一个接受L的最小DFA。这个DFA是惟一的么？,2020/7/23,480,5.3.1 Myhill-Ne

55、rode 定理,推论5-2 对于任意的 RL L，在同构意义下，接受L的最小DFA是惟一的。 证明： 接受L的最小DFA M=(Q，q0，F)的状态数与RL的指数相同，也就是说，这个最小DFA的状态数与Myhill-Nerode定理证明中构造的M=(*/RL，x|xL)的状态数是相同的。,2020/7/23,481,5.3.1 Myhill-Nerode 定理,DFA同构是指这两个DFA的状态之间有一个一一对应，而且这个一一对应还保持状态转移也是相应一一对应的。也就是说，如果q与w对应，p与z对应，当(q，a)=p时，必定有(w，a)=z。 这两个DFA是同构。定义映射f f(q)=f(q0，

56、x)= (，x)=x (q0，x)=q,2020/7/23,482,5.3.1 Myhill-Nerode 定理,f为Q与*/RL之间的一一对应 如果(q0，x)=(q0，y)，则x RM y 由于RM是RL的加细，所以，x RL y 故，x=y，即，(，x)=(，y)。 如果，(q0，x)(q0，y) 则，(，x)(，y) 即，xy 否则，|*/RM |*/RL |。,2020/7/23,483,5.3.1 Myhill-Nerode 定理,如果(q，a)=p，f(q)= x，必有f(p)=xa qQ，如果，f(q)=f(q0，x)=x 所以， a，如果， p=(q，a)=(q0，x)，a)

57、=(q0，xa) 则f(p)=f(q，a)= f(q0，x)，a)=f(q0，xa)=xa 即，如果M在状态q读入字符a时进入状态p，则M在q对应的状态f(q0，x)=x读入字符a时，进入p对应的状态f(q0，xa) )=xa。所以，f是M和M之间的同构映射。,2020/7/23,484,5.3.2 DFA的极小化,可以区分的(distinguishable) 状态 设DFA M=(Q，q0，F)，如果x*， 对Q中的两个状态q和p，使得(q，x)F 和(p，x)F中，有且仅有一个成立，则称p和q是可以区分的。否则，称q和p等价。并记作qp 。,2020/7/23,485,5.3.2 DFA的

58、极小化,算法5-1 DFA的极小化算法 算法思想：扫描所有的状态对，找出所有的可区分的状态对，不可取分的状态对一定是等价的。 输入：给定的DFA。 输出：可区分状态表。 主要数据结构：状态对的关联链表；可区分状态表。,2020/7/23,486,5.3.2 DFA的极小化,主要步骤 for (q，p)F(Q-F) do 标记可区分状态表中的表项(q，p)； for(q,p)FF(Q-F) (Q-F) (2) NEWV=A|AwP且wT*； (3) while OLDVNEWV do begin (4) OLDV=NEWV； (5) NEWV=OLDVA|AP且(TOLDV) * end (6)

59、 V=NEWV； (7) P= A| AP且 AV且(TV)*,2020/7/23,554,6.2.1 去无用符号,第(3)条语句控制对NEWV进行迭代更新。第一次循环将那些恰经过两步可以派生出终极符号行的变量放入NEWV；第二次循环将那些恰经过三步和某些至少经过三步可以派生出终极符号行的变量放入NEWV；，第n次循环将那些恰经过n步和某些至少经过n+1步可以派生出终极符号行的变量放入NEWV。这个循环一直进行下去，直到所给文法G中的所有可以派生出终极符号行的变量都被放入NEWV中。,2020/7/23,555,6.2.1去无用符号,定理 6-4 算法6-1是正确的。 证明要点：首先证明对于任意AV，A被放入V中的充要条件是存在wT，An w。再证所构造