正则语言类在并、连结和星号运算下是封闭的。其证明采用的都是非确定型有穷自动机(简记作NFA)理论。M.Sipser在《Introduction to the Theory of Computation》中用确定型有穷自动机(简记作DFA)理论给出了正则语言类在并运算下的封闭性证明,但没有用确定型有穷自动机理论给出正则语言类在连结和星号运算下的封闭性证明。本文试图尝试完成这一工作。
定义1 如果一个语言被一台有穷自动机识别,则称它是正则语言。
定义2 设A和B是两个语言,正则运算连结和星号是指:
连结:A·B ={xy:x∈A∧y∈B}
星号:A* ={x1x2…xi…xk:k≥0且每一个xi∈A}
定义3 确定型有穷自动机是一个5元组(Q,Σ,δ,q0,F),其中
1)Q是一个有穷集合,叫做状态集。
2)Σ是一个有穷集合,叫做字母表。
3)δ:Q×Σ→Q是转移函数。
4)q0∈Q是起始状态。
5)F
定理1 正则语言类在连结运算下封闭。
分析:假设确定型有穷自动机DFA M1识别A1,DFA M2识别A2,M.Sipser认为:“设计的(确定型)有穷自动机M不是当M1或M2接受输入时接受输入,而应该是当它的输入可以被分成两段,M1接受第一段M2接受第二段时,M才接受。问题是M不知道在什么地方把它的输入分开(即,在什么地方第一段结束和第二段开始)。”因此,M.Sipser放弃了用确定型有穷自动机理论来证明正则语言类在连结运算下的封闭性;而引入了非确定性的新技术,用非确定型有穷自动机理论来完成其证明。
我们认为用确定型有穷自动机理论是可以证明正则语言类在连结运算下的封闭性的。设想自己就是这样的一台确定型有穷自动机M,同时模拟M1和M2。当输入符号w1w2…wn一个接一个地来到时,我们首先记住M1和M2的起始状态q1和p1。对于输入w1,因为它既可能属于A1又可能属于A2。如果它属于A1,假定δ1 (q1, w1)=q2,那么M1和M2分别处于q2和p1状态;如果它属于A2,假定δ2 (p1, w1)=p2,那么M1和M2分别处于q1和p2状态。这时,我们需要记住的状态是q2p1和q1p2。与此类似,对于输入w2,当处于状态q2p1时,可能进入q3p1和q2p2状态;当处于状态q1p2时,可能进入q2p2和q1p3状态。这时,我们需要记住的状态是q3p1、q2p2和q1p3。……所以,我们需要记住的所有状态是M1的状态集和M2的状态集的迪卡儿积的所有非空子集。当输入结束,如果我们所记住的状态中存在qipj,其中qi属于M1的接受状态并且pj属于M2的接受状态,则接受这一字符串;否则,拒绝。
证明:设DFA M1识别A1,DFA M2识别A2,其中
M1=(Q1,Σ,δ1,q1,F1), M2=(Q2,Σ,δ2,p1,F2)
构造识别A1·A2的DFA M,这里M =(Q,Σ,δ,q,F)。
1) Q = {x:x∈P(y)-{φ}, y ={r1r2:r1∈Q1∧r2∈Q2}}
2) 字母表Σ与M1 、M2的相同。
3) 转移函数δ定义如下:对于每一个状态x∈Q和每一个a∈Σ,令
δ(x,a)={qipj+1:qipj∈x,pj+1=δ2 (pj,a)}∪{qi+1pj:qipj∈x,qi+1=δ1 (qi,a)}
4)q={q1p1}
5)F={x:x∈P(y)∧
由M的构造,不难验证:对任一字符串w1w2…wn,如果w1w2…wn∈A1·A2,当且仅当M接受w1w2…wn。
定理2 正则语言类在星号运算下封闭。
分析:假设确定型有穷自动机DFA M1识别A,我们要设计一台识别A*的DFA M。设想自己就是这样的一台确定型有穷自动机M。当输入符号w1w2…wn一个接一个地来到时,我们首先记住M的起始状态q1。对于输入w1,假定δ1 (q1, w1)=q2,则进入q2;……,对于输入wi,δ1 (qi, wi)=qi+1,如果qi是M1一接受状态,则我们除了须记住状态qi+1外,还必须记住分叉δ1 (q1, wi),因为w1w2…wi-1可能是语言A中的字符串,也可能是语言A中的字符串的前一部分。因此,此时我们要记住的状态是M1中的状态qi+1和δ1 (q1, wi)。如此进行下去,每遇到M1一接受状态,都发生分叉。这样,我们实际需记住的全部状态为所有M1状态的非空子集。当输入结束,如果所记住的M1的状态子集中存在一M1一接受状态,则接受;否则,拒绝。
另外,在M中增加接受状态q0 。增加接受状态q0是为了保证DFA M接受空串
证明:设DFA M1识别A,其中
M1=(Q1,Σ,δ1,q1,F1)
构造识别A*的DFA M,这里M =(Q,Σ,δ,q,F)。
1) Q =(P(Q1)-{φ})∪{q0}
2) 字母表Σ与M1 的相同。
3) 转移函数δ定义如下:对于每一个状态Qi∈(P(Q1)-{φ})∪{q0}和每一个a∈Σ,令
δ(q0,a) ={δ1 (q1,a)}
δ(Qi,a)={qi+1:qi+1=δ1 (qi,a),qi∈Qi } 若﹁
或={qi+1:qi+1=δ1 (qi,a),qi∈Qi }∪{δ1 (q1,a)} 若﹁
4)q=q0
5)F={Qj: Qj∈P(Q1)∧
由M的构造,不难验证:对任一字符串w1w2…wn,如果w1w2…wn∈A*,当且仅当M接受w1w2…wn。
在以上两定理的构造性证明中,都可将状态集Q简化。实际设计时,在状态图中将无箭头射入的状态删去,这不会影响计算功能。
通过这两个证明,我们看到用确定型有穷自动机理论证明正则语言类在连结和星号运算下的封闭性比用非确定型有穷自动机理论证明正则语言类在连结和星号运算下的封闭性,其状态集要大得多,这可以使我们对非确定型有穷自动机的简单性有更加清楚的认识;另一方面,通过用确定型有穷自动机理论对正则语言类在连结和星号运算下的封闭性证明,我们也可以更加深刻地体会到确定型有穷自动机潜在的强大计算能力。
【参考文献】
[1] 张立昂等译 [美]Michael Sipser著 《计算理论导引》 机械工业出版社2000年版。
[2] 刘田等译 [美]Harry R.Lewis, Christos H.Papadimitriou著 《计算理论基础》 清华大学出版社2000年版。
[3] [美]Harry R.Lewis, Christos H.Papadimitriou著 《Elements of the Theory of Computation》 清华大学出版社1999年版。
[4] 许明贤等译 [英]罗杰·彭罗斯著 《皇帝新脑》 湖南科学技术出版社1996年版。
(原载《自动化理论、技术与应用》第8卷,解放军出版社2001年6月)