形式语言与自动机ch3.7-3.9a精要.ppt

* * College of Computer Science Technology, BUPT 通过合并等价的状态进行 DFA 的优化 举例 划分结果： { 1, 2 }, {3}, {4}, {5}, { 6, 7 } 等价的状态偶对为： （1, 2）,（6, 7） 新的状态集合： [1], [3], [4], [5], [6] * * College of Computer Science Technology, BUPT 最小化的 DFA 课堂练习 最小化下列 DFA: 参考结果 * * College of Computer Science Technology, BUPT 针对正则语言的 Pumping 引理 正则语言应满足的一个必要条件 用于判定给定的语言不是正则集。 物理意义：当给定一个正则集和该集合上一个足够长的字符串时，在该字符串中能找到一个非空的子串，并使子串重复，从而组成新的字符串。该新串必在同一个正则集内。 定理： 设L是正则集，存在常数k，对字符串ω∈Ｌ 且｜ω｜≥ｋ，则ω可写成ω1ω0ω２，其中｜ω1ω0｜≤ｋ， ｜ω0｜＞０，对所有的ｉ≥0有ω1ω0iω2∈Ｌ。 证明 设 L 是 DFA D = (Q, T, ?, q0 , F ) 的语言， 取 k = |Q| 即可.  * * College of Computer Science Technology, BUPT DFA 的“Pumping”特性 设 DFA D = (Q, T, ?, q0 , F ), |Q|=n. 对于任一长度不小于 n 的字符串 w = a1a2…am , 其中 m?n, ak?T (1? k ?m), q?Q , 考察如下状态序列 p0=q p1=?(q, a1) p2=?(q, a1a2) … pn=?(q, a1a2…an ) pn+1=?(q, a1a2…an+1 ) … pm=?(q, a1a2…am ) 由pigeonhole 原理, p0, p1, p2, …, pn 中至少有两个状态是重复的，即存在 i, j, 0?i?j?n, pi=pj . “pumping” 特性： 任一长度不小于状态数目 的字符串所标记的路径上， 必然出现重复的状态. * * College of Computer Science Technology, BUPT DFA 的“Pumping”特性 “pumping” 特性：如前,设 DFA D = (Q, T, ?, q0 , F ), |Q|=n, w = a1a2…am (m?n), 则存在 i, j, 0?i?j?n, pi=pj , 其中pk=?(p0, a1a2…ak ) , 0?k?m. 若假定p0 = q0 , pm?F, 即w?L(D). 令 w = xyz, 其中： x = a1a2…ai , y = ai+1ai+2…aj , z = aj+1aj+2…am 则对任何k ? 0，都有 xykz ?L(D). (参考下图) p0 pi pm x = a1a2…ai y = ai+1ai+2…aj z=aj+1aj+2…am * * College of Computer Science Technology, BUPT Pumping 引理的应用 （ 用于证明某个语言 L 不是正规语言） 证明步骤 　 1. 选任意的n. 2. 找到一个满足以下条件的串w?L (长度至少为n). 3. 任选满足w = xyz ? y?? ? |xy| ? n 的x,y,z 4. 找到一个 k ?0, 使 xykz ? L. 举例 证明L={ anbn | n≥1 }不是正则集. 证明: 由泵浦引理，假设L是正则集，则对足够大的n， anbn可写成ω1ω0ω2，其中0 |ω0|，|ω1ω0|≤n，|ω|= 2n n ω0中不可能含 b+，否则不满足0 |ω1ω0|≤n. ω0只可能取 a+，设|ω0|=k≥1，k为常数， 取i=0，有ω1ω00ω2 = ω1ω2 = an-kbn，此时，a，b字符个数不同,即新组成的串ω1ω2?L. ∴ 与假设矛盾，故L不是正则集. * * College of Computer Science Technology, BUPT Pumping 引理的应用