形式语言 第4 正则表达式.ppt

* * 4.3.1 RE到FA的等价变换 r=r1* * * 4.3.1 RE到FA的等价变换 按照定理4-1证明给出的方法构造一个给定RE的等价FA时，该FA有可能含有许多的空移动。 可以按照自己对给定RE的“理解”以及对FA的 “理解” “直接地”构造出一个比较“简单”的FA。 定理证明中所给的方法是机械的。由于“直接地”构造出的FA的正确性依赖于构造者的“理解”，所以它的正确性缺乏有力的保证。 * * 4.3.1 RE到FA的等价变换 例 4-3 构造与 (0+1)*0+(00)*等价的FA。 * * 4.3.1 RE到FA的等价变换 按照对(0+1)*0+(00)*的“理解” “直接地”构造出的FA。 * * 4.3.2 RL可以用RE表示 计算DFA的每个状态对应的集合——字母表的克林闭包的等价分类，是具有启发意义的。 这个计算过程难以“机械”地进行。 计算q1到q2的一类串的集合：Rkij 。 图上作业法。 * * 4.3.2 RL可以用RE表示 定理4-2 RL可以用RE表示。 设DFA M=({q1，q2，…，qn}，∑，δ，q1，F) Rkij={x|δ(qi，x)=qj而且对于x的任意前缀y(y≠x，y≠ε)，如果δ(qi，y)=ql，则l≤k}。 * * 4.3.2 RL可以用RE表示 R0ij= {a|δ(qi，a)=qj} 如果i≠j {a|δ(qi，a)=qj}∪{ε} 如果i=j Rkij= Rk-1ik( Rk-1kk)* Rk-1kj ∪ Rk-1ij * * 4.3.2 RL可以用RE表示 图上作业法 启示 * * 4.3.2 RL可以用RE表示 图上作业法操作步骤 ⑴ 预处理： ① 用标记为X和Y的状态将M“括起来”： 在状态转移图中增加标记为X和Y的状态，从标记为X的状态到标记为q0的状态引一条标记为ε的弧；从标记为q(q∈F)的状态到标记为Y的状态分别引一条标记为ε的弧。 ② 去掉所有的不可达状态。 * * 4.3.2 RL可以用RE表示 ⑵ 对通过步骤(1)处理所得到的状态转移图重复如下操作，直到该图中不再包含除了标记为X和Y外的其他状态，并且这两个状态之间最多只有一条弧。 并弧 将从q到p的标记为r1，r2，…，rg并行弧用从q到p的、标记为r1+r2+…+rg的弧取代这g个并行弧。 * * 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的弧代替。 * * 4.3.2 RL可以用RE表示 去状态3 如果图中只有三个状态，而且不存在从标记为X的状态到达标记为Y的状态的路，则将除标记为X的状态和标记为Y的状态之外的第3个状态及其相关的弧全部删除。 * * 4.3.2 RL可以用RE表示 ⑶ 从标记为X的状态到标记为Y的状态的弧的标记为所求的正则表达式。如果此弧不存在，则所求的正则表达式为Φ。 * * 4.3.2 RL可以用RE表示 例 4-4 求图4-14所示的DFA等价的RE 。 * * 4.3.2 RL可以用RE表示 预处理。 * * 4.3.2 RL可以用RE表示 去掉状态q3。 * * 4.3.2 RL可以用RE表示 去掉状态q4。 * * 4.3.2 RL可以用RE表示 合并从标记为q2的状态到标记为Y的状态的两条并行弧。 * * 4.3.2 RL可以用RE表示 去掉状态q0。 * * 4.3.2 RL可以用RE表示 并弧。 * * 4.3.2 RL可以用RE表示 去掉状态q1。 * * 4.3.2 RL可以用RE表示 去掉状态q2。 1*0(11*0)*0((00*111*0+00*10+11*0)(11*0)*0)(00*+00*1)就是所求。 * * 4.3.2 RL可以用RE表示 几点值得注意的问题 ⑴ 如果去状态的顺序不一样，则得到的RE可能在形式是不一样，但它们都是等价的。 ⑵ 当DFA的终止状态都是不可达的时候，状态转移图中必不存在从开始状态到终止状态的路。此时，相应的RE为Φ。 ⑶ 不计算自身到自身的弧，如果状态q的入度为n，出度为m，则将状态q及其相关的弧去掉之后，需要添加n*m条新弧。 * * 4.3.2 RL可以用RE表示 ⑷ 对操作的步数施归纳，可以证明它的正确性。 推论4-1 正则表达式与FA、正则文法等价，是正则语言的表示模型。 * *