第5 章 正则语言的性质 在讨论正则语言的性质时,一般分两类进行。第一类是由于直接用有穷的形式表达无 穷所表现出来的性质,这种性质用正则语言的泵引理表示。除了基本的泵引理外,还有一种 形式可以称为扩充的泵引理,其证明与基本泵引理的证明具有相同的思想。除了证明泵引 理的正确性外,更重要的是应用泵引理证明给定的语言不是正则语言。这涉及发现特殊串 的问题。 正则语言性质的第二类是关于一系列运算的封闭性。包括对并、乘积、闭包、补、交等基 本运算的封闭性和对正则代换、同态、逆同态等运算的封闭性。对应不同的运算,其封闭性 证明将使用正则语言的不同描述方法。 本章讨论的第二部分内容是通过给定正则语言本身结构的固有特征寻求不同表示的一 致性。这种一致性是通过该语言确定的右不变等价关系RL 表现出来的。它将相应字母表 上的所有字符串分成一些等价类,而这一分法是由语言L 决定的,所以说它表达的是L 本 身结构的固有特征。由于在一般情况下,等价类的直接划分比较困难,而且这种困难导致了 对其进行自动化的困难,所以,人们将其转换为寻求接受该语言的、状态最少的、确定的有穷 状态自动机———最小DFA 的问题。而且在同构意义下,最小DFA 是唯一的。这里给出的 根据DFA 去构造其相应最小DFA 的方法是可以由计算机系统自动完成的。这一部分的 内容可以分成Myhill-Nerode定理与FA 的极小化。 本章的第三部分内容简要介绍正则语言相关的几个判定问题。包括空否、有穷否、两个 DFA 等价否以及成员关系等。 本章的内容比较多,其中最基本的有:正则语言的泵引理及其应用,正则语言的封闭性。 这些是读者应该掌握的,尤其是相关证明的基本思想。所以,这些可以作为本章的重点内 容。如果时间和精力允许,还可以将Myhill-Nerode定理的理解与应用作为重点。本章中 比较难的内容是关于正则代换、同态、逆同态的封闭性证明。主要原因是相关的概念比较 生,也比较复杂。另外,Myhill-Nerode定理及其应用涉及DFA 以及语言决定的等价关系 对语言的结构特征的刻画问题,加上用等价关系进行等价分类也是比较难的问题,所以,这 一部分也是比较难的。 84 形式语言与自动机理论教学参考书(第4版) 5.正则语言的泵引理 1 1. 知识点 (1)当DFA 识别的语言 L 是无穷语言时, L 中必定存在一个足够长的句子,使得DFA 在识别该句子的过程中,肯定要重复地经过某些状态。 (2)泵引理给出的是正则语言的“必要条件”而不是“充分条件”,它只能用来证明一个 语言不是正则语言,不能用来证明一个语言是正则语言。 2. 主要内容解读 5-1(泵引理pumpinglemma) 设 L 为一个正则语言,则存在仅依赖于 L 的正整 数 N ,对于.z∈L, z|≥ N , v,满足: (1)z=uvw 。 如果|则存在u,w, (2)|uv|≤ N 。 (3)|v|≥1 。 (4)对于任意整数i≥0,viw∈L。 (5) N 不大于接受 L 的小DFAM 的状态数。 证明要点:DFA 在处理一个足够长的句子的过程中,必定会重复地经过某些状态。换最(u) 句话说,在DFA 的状态转移图中,必定存在一条含有回路的从启动状态到某个终止状态的 路。由于含有回路,所以,DFA 可以根据实际需要沿着这个回路循环运行,相当于这个回路 中弧上的标记构成的非空子串可以重复任意次。 值得反复强调的一点是,泵引理给出的是RL 的必要条件,所以,该引理只能用来证明 给定的语言不是RL 。条件|uv|≤ N 表明,可以用来“泵进”和“泵出”的子串 v 在句子 z 的 前 N 个字符中是存在的,所以,讨论可以集中在 z 的前 N 个字符上进行。然而,如果在这 N 个字符中找不到引起矛盾的v,并不能说明给定的语言是RL,因为其他类型的某个具体 语言也是满足这一要求的———泵引理给出的是必要而非充分条件。 另外,从泵引理的证明不难看出,可以在被判定语言的句子 z 的任何位置截取一个子 串,只要这个子串足够长,就一定能在这个子串中找到可以用来“泵进”和“泵出”的子串v。 事实上,不妨取z=z1z2z3∈L,|= N ,a1a2…aN ,将DFA 开始扫描到z2 的首字符 时所处的状态记为q0,并且令 z2|z2= ' q0,=qh 则在状态序列q0,(') q2,…, δ('a1a2…ah ) 不妨令最早相等的两个状态为 和qk ,则 q1,qN 中就必定有重复的。例如, qj k