[工学]形式语言与自动机07章 正则语言的性质-1.ppt

第七章 正则语言 7.1 正则语言与有限状态自动机 7.2 正则语言的泵浦引理 7.1 正则语言与有限状态自动机 正则表达式RE与有限状态自动机FSAM(或NDAM)是等价的。 7.1.1 正则表达式与有限状态自动机 例7-1 简单的正则表达式和对应的有限状态自动机的情况。 正则表达式0对应的有限状态自动机 例7-1(续) 正则表达式0+1对应的有限状态自动机? 例7-1(续) 正则表达式0*对应的有限状态自动机 定理7-1 设r是一个正则表达式，则存在一个带?动作的有限状态自动机，有 L(NDAM) = S(r) 例7-2 构造与正则表达式10*+0等价的?-NDAM。 例7-2(续) 分别与10*和10*+0等价的?-NDAM 回顾 正则表达式r和它所表达的正则集S(r)的定义 ?是一个正则表达式，S(?) = ? ； ? 是一个正则表达式，S(?) = {?}； 若a ? ?，则a是一个正则表达式，S(a) = {a}； 若r1和r2是正则表达式，则r1 + r2是正则表达式，S(r1 + r2) = S(r1) ? S(r2) 若r1和r2是正则表达式，则r1r2是正则表达式，S(r1r2) = S(r1)S(r2) 若r是正则表达式，则(r)*是正则表达式，S((r)*) = (S(r))*； 证明 基础 设正则表达式r的构造次数n为0，即r没有经过任何运算（联合、连接和闭包）而得，因此， r只能为?, ?，或者a ? ? 。 1) r = ? 2) r = ? 3) r = a 归纳 假设结论对n ? k (k ? 0)成立，即构造次数不大于k的正则表达式均有一个?-NDAM M与之等价，不失一般性，假设M仅有一个开始状态与一个终止状态，则当n = k + 1，根据r最后一次运算的形式，分为三种情况： 归纳(续) L(M) = L(M1) ? L(M2) = S(r1 + r2 ) 归纳(续) 2)r = r1r2 L(M) = L(M1)L(M2) = S(r1r2 ) 归纳(续) 2)r = r1* L(M) = L(M1)* = S(r1* ) 证明(续) 根据r最后一次运算的三种情况，可知，当n = k + 1，结论也成立。 所以，对于正则表达式r，存在一个等价的?-NDAM M。证毕。 看图讨论 是否可以去掉例7-2图中某些?？可举例说明。 从本图还可以联想到其它领域或方向的哪些问题/术语？ 作业 习题4(1) 定理7-2 如果语言L被一个FSAM所接收，则语言L可以用一个正则表达式来表示。 基本替换 例 求与下图所示的FSAM等价的正则表达式。 预处理 增加两个状态X ，Y及相应空移动边(不存在不可到达状态) 去掉状态q3 使用“去状态2”，q = q2 ，p= q3 ，t=Y| q4 去掉状态q4 使用“去状态1” ，q = q2 ，p= q4 ，t=Y| q1 | q0 并弧 去掉状态q0 使用“去状态2”，q = q2 | q1 | X，p= q0 ，t=q1 并弧 去掉状态q1 使用“去状态2”，q = q2 | X，p= q0 ，t=q2 去掉状态q2 使用“去状态2” 讨论 在哪些情况需要使用“去状态3”？ 如何选择去状态顺序减少工作量？ 说明 如果删除状态的顺序不一致，最后得到的正则表达式可能在形式上不一样，但它们都是等价的；而且删除状态和并弧操作也没有绝对的先后顺序，一般地，在状态图的处理过程中，优先地执行并弧操作，会使后继的删除状态简单一些，因为增加的弧会少一些。 当FSAM的接收状态都是不可到达状态时，状态转换图中肯定不存在从开始状态到某个接收状态的路；使用“图上作业”方法，最终会去掉除状态X和状态Y以外的所有状态和弧，这种情况下，对应的正则表达式为Φ。 说明(续) 不计算自身到自身的弧，如果状态q的入度为n，出度为m，则将状态q及相关的弧去掉之后，需要增加n*m条新弧。 对于操作步骤进行归纳假设，不难证明“图上作业”方法的正确性。 按照“图上作业”的方法，最后，没有将标记为X和Y的两个状态去掉。 “图上作业”的方法，也可以当作一个算法，可以利用计算机实现，有兴趣的读者可以进行试验。 作业 求与图6-11自动机等价的正则表达式。 7.1.2 正则语言的等价模型 正则语言有5种等价模型：正则文法（右线性文法）RG，正则表达式RE、确定的有限状态自动机FSAM，不确定的有限状态自动机?-NDAM，带?动作的有限状态自动机? -NDAM。 正则语言的5种等价模型的转换关系可以用图7-28表示。 转换关系 7.2 正则语言的泵浦引理 一个FSAM只有有穷个状态，当该FSAM识别的语言L是无穷语言时，L中必定存在一个足够长(大于DFA的可达状态数)的句子，使得FSAM在识别该句子的过