形式语言与自动机DFA与NFA等价性及正则运算封闭性.ppt

9/15/2019 9:05 AM,,1,形式语言与自动机,授课 人： 王 良 民MAIL:,9/15/2019 9:05 AM,,2,第五章 DFA与NFA等价性 及正则运算封闭性,5.1 NFA 与DFA的等价性 5.2 正则语言类在正则运算下的封闭性 5.2.1并运算下的封闭性 5.2.2 连接运算下的封闭性 5.2.3 星号运算下的封闭性,9/15/2019 9:05 AM,,3,NFA、DFA识别相同的语言类。这个等价性是出人意料的因为NFA好像比DFA的能力强，因此我们猜想它能识别更多的语言，但是却是非常有用的因为对于给定的语言，描述识别这个语言的NFA又是比描述识别这个语言的DFA要容易得多。 如果两台机器识别相同的语言，则称它们是等价的。,9/15/2019 9:05 AM,,4,定理1 每一台非确定型有穷自动机都有一台等价的确定型有穷自动机 证明思路：设一个语言被一台NFA识别，必须证明存在一台DFA也识别这个语言。基本想法就是把NFA转换成模拟它的DFA。,9/15/2019 9:05 AM,,5,“自己即自动化机”如果我们自己是一台DFA自动机，如何模拟这台NFA？ 在处理输入串的过程中，你需要记住什么？放着手指的状态的集合NFA中用多个“手指”放在每一个可能的活动状态上，用这种方法记住各个计算分支 设是NFA的状态数，它有2k个状态子集。每一个子集对应模拟这台NFA的DFA必须记住的一种可能性，即这个DFA有2k个状态。幂集？ 还需要给出起始状态和接受状态,9/15/2019 9:05 AM,,6,证明：设N = (Q, , , q0, F )是识别语言A的NFA，要构造一台DFA为M，识别A。 在给出完整的构造以前，现考虑比较容易的情况，假设N没有空语句箭头。以后再把箭头考虑进来。 构造M = (Q, , , q0, F ) (1) Q=P(Q) 幂集，表示的M状态是N的一个状态子集。,9/15/2019 9:05 AM,,7,(2) 对于RQ和a，令 (R, a) = qQ | 存在rR,使得q (r, a) 如果R是M的一个状态，则它是N的一个状态子集。 当M在状态R读到符号a时，(R, a)给出a把R中的状态转移到 由于每一个状态可以转移到一个状态子集，所以取所有这些子集的并。 上述表达式也可以写成：,9/15/2019 9:05 AM,,8,q0 = q0 M开始时所在的状态对应于只含有N的起始状态的集合 F= RQ| R包含N的一个接受状态 如果当时N的可能状态中有一个接受状态，则机器M接受,9/15/2019 9:05 AM,,9,上述工作完成了没有箭头的NFA转化成DFA机器M。现在考虑箭头，现引入一个记号： E(R) = q | 从R出发沿着0个或多个箭头可以到达q 对于M的任意一个状态R， E(R)为从R出发只沿着箭头可以达到的状态集合，修改M的转移函数，使得在每一步之后，在沿着箭头可以达到的所有状态集合上也“放上手指”，用E( (r, a)代替 (r, a)： (R, a) = qQ |存在rR,使得qE( (r, a),9/15/2019 9:05 AM,,10,此外，还需要修改M的起始状态，增加由N的起始状态出发沿着箭头可以到达的所有状态上。从形式上说，就是把q0改为E(q0) 至此，完成与NFA等价的DFA的构造，在计算的每一步，M进入的状态明显地对应于N此时可能处于的状态子集。证毕。,9/15/2019 9:05 AM,,11,说明： 上述证明使用的构造较为简单，可以比较显然的观察到其正确性。 对于更复杂的构造，需要证明它是否如所声称的那样工作。 通常这种证明采用对计算的步数做归纳的方式进行，后面将给一个这样的例子。,9/15/2019 9:05 AM,,12,推论：一个语言是正则的，当且仅当由一台非确定型有限状态自动机识别它。 例题1：用前面例子上的机器N4来说明把NFA转换成DFA的过程。,9/15/2019 9:05 AM,,13,N4 = 1,2,3,a,b,1,1 1,2,3为3个元素的状态集，所以相应的DFA的状态集有23个元素 空集，1, 2, 3, 1,2,1,3,2,3,1,2,3 相应DFA的起始状态E(1), 表示状态1本身加上由1出发通过箭头能到达的所有状态 相应DFA的接受状态是上述状态中所有包含N4接受状态1的状态子集。 1,1,2,1,3,1,2,3 相应DFA的转移函数每一个状态遇到输入a到一个地方，遇到输入b到一个地方。,9/15/2019 9:05 AM,,14,可以简化这台机器, 删掉没有箭头射入的两个状态：1,1, 2,9/15/2019 9:05 AM,,15,重新排列：,9/15/2019 9:05 AM,,16,第五章 DFA与NFA等价性 及正则运算封闭性,5.1 NFA 与DFA的等价性 5.2 正则语言类在正则运算下的封闭性 5.2.1并运算下的封闭性 5.2.2 连接运算下的封闭性 5.2.3 星号运算下的封闭性,9/15/2019 9:05 AM,,17,前面已经说过，正则语言在正则运算下是封闭的。正则运算有三个运算：并运算、连接运算以及星号运算。我们仅完成了并运算的证明，而放弃了连接运算封闭性的证明，因为太复杂。 有了非确定性，能让证明容易多了。,9/15/2019 9:05 AM,,18,第五章 DFA与NFA等价性 及正则运算封闭性,5.1 NFA 与DFA的等价性 5.2 正则语言类在正则运算下的封闭性 5.2.1并运算下的封闭性 5.2.2 连接运算下的封闭性 5.2.3 星号运算下的封闭性,9/15/2019 9:05 AM,,19,定理1：正则语言类在并运算下封闭。 证明思路：有两个正则语言A1和A2，要证明A1A2是正则的。想法是对A1和A2取两台NFA，记为N1和N2，把他们合并为一台新的NFA，记为N。 当N1或N2接受输入时，机器N应该接受这个输入。 新机器有新的起始状态，用空串箭头到老机器的起始状态。,9/15/2019 9:05 AM,,20,新机器用这种非确定性地猜想这两台老机器中哪一台接受这个输入。如果他们两台中有一个接受，那么N也接受。下图给出了这个构造。,9/15/2019 9:05 AM,,21,证明：设N1 = (Q1, , 1, q1, F1 )识别A1，N2 = (Q2, , 2, q2, F2 )识别A2。构造识别A1A2的自动机N = (Q, , , q0, F )。 (1) Q = q0Q1Q2 (2) q0是N的起始状态 (3) F = F1F2 (4) 定义如下：对于每一个qQ每一个a, 下式成立：,9/15/2019 9:05 AM,,22,显然，A1A2是自动机N识别的语言，因此是正则语言。,9/15/2019 9:05 AM,,23,第五章 DFA与NFA等价性 及正则运算封闭性,5.1 NFA 与DFA的等价性 5.2 正则语言类在正则运算下的封闭性 5.2.1并运算下的封闭性 5.2.2 连接运算下的封闭性 5.2.3 星号运算下的封闭性,9/15/2019 9:05 AM,,24,定理2：正则语言类在连结运算下封闭。 证明思路：有两个正则语言A1和A2，要证明A1A2是正则的。想法是对A1和A2取两台NFA，记为N1和N2，把他们合并为一台新的NFA，记为N。 当输入分为两段，第一段被N1接受，而第二段被N2接受时，机器N接受。 新机器以N1的起始状态为起始状态， N1的每一个接受状态增加一个箭头到N2的起始状态。,9/15/2019 9:05 AM,,25,9/15/2019 9:05 AM,,26,证明：设N1 = (Q1, , 1, q1, F1 )识别A1，N2 = (Q2, , 2, q2, F2 )识别A2。构造识别A1oA2的自动机N = (Q, , , q0, F )。 (1) Q = Q1Q2 (2) q1是N的起始状态 (3) F = F2,9/15/2019 9:05 AM,,27,(4) 定义如下：对于每一个qQ每一个a, 下式成立：,9/15/2019 9:05 AM,,28,第五章 DFA与NFA等价性 及正则运算封闭性,5.1 NFA 与DFA的等价性 5.2 正则语言类在正则运算下的封闭性 5.2.1并运算下的封闭性 5.2.2 连接运算下的封闭性 5.2.3 星号运算下的封闭性,9/15/2019 9:05 AM,,29,定理3：正则语言类在星号运算下封闭。 证明思路：有正则语言A1，要证明A1*是正则的。想法是对A1取台NFA，记为N1，构造一台新的NFA，记为N，能识别A1*。 当输入分为若干段，每一段都被N1接受时，机器N接受。 机器N1的每一个接受状态都添加回到起始状态的箭头。 增加一个新状态为N的起始状态，添加一个指向N1的起始状态的箭头(使接受)，,9/15/2019 9:05 AM,,30,9/15/2019 9:05 AM,,31,证明：设N1 =