正则语言类在并、连结和星号运算下是封闭的。其证明采用的都是非确定型有穷自动机（简记作NFA）理论。M.Sipser在《Introduction to the Theory of Computation》中用确定型有穷自动机（简记作DFA）理论给出了正则语言类在并运算下的封闭性证明，但没有用确定型有穷自动机理论给出正则语言类在连结和星号运算下的封闭性证明。本文试图尝试完成这一工作。

定义1 如果一个语言被一台有穷自动机识别，则称它是正则语言。

定义2 设A和B是两个语言，正则运算连结和星号是指：

连结:A·B ＝{xy:x∈A∧y∈B}

星号:A^* ＝{x₁x₂…x_i…x_k:k≥0且每一个x_i∈A}

定义3 确定型有穷自动机是一个5元组（Q，Σ，δ，ｑ₀，F），其中

1）Q是一个有穷集合，叫做状态集。

2）Σ是一个有穷集合，叫做字母表。

3）δ：Q×Σ→Q是转移函数。

4）ｑ₀∈Q是起始状态。

5）F Q是接受状态集。

定理1 正则语言类在连结运算下封闭。

分析：假设确定型有穷自动机DFA M₁识别A₁，DFA M₂识别A₂，M.Sipser认为：“设计的（确定型）有穷自动机M不是当M₁或M₂接受输入时接受输入，而应该是当它的输入可以被分成两段，M₁接受第一段M₂接受第二段时，M才接受。问题是M不知道在什么地方把它的输入分开（即，在什么地方第一段结束和第二段开始）。”因此，M.Sipser放弃了用确定型有穷自动机理论来证明正则语言类在连结运算下的封闭性；而引入了非确定性的新技术，用非确定型有穷自动机理论来完成其证明。

我们认为用确定型有穷自动机理论是可以证明正则语言类在连结运算下的封闭性的。设想自己就是这样的一台确定型有穷自动机M，同时模拟M₁和M₂。当输入符号ｗ₁ｗ₂…ｗ_n一个接一个地来到时，我们首先记住M₁和M₂的起始状态q₁和p₁。对于输入ｗ₁，因为它既可能属于A₁又可能属于A₂。如果它属于A₁，假定δ₁ (q₁, ｗ₁)＝q₂，那么M₁和M₂分别处于q₂和p₁状态；如果它属于A₂，假定δ₂ (p₁, ｗ₁)＝p₂，那么M₁和M₂分别处于q₁和p₂状态。这时，我们需要记住的状态是q₂p₁和q₁p₂。与此类似，对于输入ｗ₂，当处于状态q₂p₁时，可能进入q₃p₁和q₂p₂状态；当处于状态q₁p₂时，可能进入q₂p₂和q₁p₃状态。这时，我们需要记住的状态是q₃p₁、q₂p₂和q₁p₃。……所以，我们需要记住的所有状态是M₁的状态集和M₂的状态集的迪卡儿积的所有非空子集。当输入结束，如果我们所记住的状态中存在q_ip_j，其中q_i属于M₁的接受状态并且p_j属于M₂的接受状态，则接受这一字符串；否则，拒绝。

证明：设DFA M₁识别A₁，DFA M₂识别A₂，其中

M₁＝（Q₁，Σ，δ₁，ｑ₁，F₁）, M₂＝（Q₂，Σ，δ₂，p₁，F₂）

构造识别A₁·A₂的DFA M，这里M ＝（Q，Σ，δ，ｑ，F）。

1) Q ＝ {x:x∈P(y)－{φ}, y ＝{r₁r₂:r₁∈Q₁∧r₂∈Q₂}}

2) 字母表Σ与M₁ 、M₂的相同。

3) 转移函数δ定义如下：对于每一个状态x∈Q和每一个a∈Σ，令

δ(x,a)＝{q_ip_j+1:q_ip_j∈x,p_j+1＝δ₂ (p_j,a)}∪{q_i+1p_j:q_ip_j∈x,q_i+1＝δ₁ (q_i,a)}

4)q＝{q₁p₁}

5)F＝{x:x∈P(y)∧ z(z∈x∧z＝q_ip_j ∧q_i∈F₁∧p_j∈F₂,y＝{q_ip_j: q_i∈Q₁∧p_j∈Q₂}}

由M的构造，不难验证：对任一字符串ｗ₁ｗ₂…ｗ_n，如果ｗ₁ｗ₂…ｗ_n∈A₁·A₂，当且仅当M接受ｗ₁ｗ₂…ｗ_n。

定理2正则语言类在星号运算下封闭。

分析：假设确定型有穷自动机DFA M₁识别A，我们要设计一台识别A^*的DFA M。设想自己就是这样的一台确定型有穷自动机M。当输入符号ｗ₁ｗ₂…ｗ_n一个接一个地来到时，我们首先记住M的起始状态q₁。对于输入ｗ₁，假定δ₁ (q₁, ｗ₁)＝q₂，则进入q₂；……,对于输入ｗ_i，δ₁ (q_i, ｗ_i)＝q_i+1，如果q_i是M₁一接受状态，则我们除了须记住状态q_i+1外，还必须记住分叉δ₁ (q₁, ｗ_i)，因为ｗ₁ｗ₂…ｗ_i－1可能是语言A中的字符串，也可能是语言A中的字符串的前一部分。因此，此时我们要记住的状态是M₁中的状态q_i+1和δ₁ (q₁, ｗ_i)。如此进行下去，每遇到M₁一接受状态，都发生分叉。这样，我们实际需记住的全部状态为所有M₁状态的非空子集。当输入结束，如果所记住的M₁的状态子集中存在一M₁一接受状态，则接受；否则，拒绝。

另外，在M中增加接受状态ｑ₀ 。增加接受状态ｑ₀是为了保证DFA M接受空串 。为什么没有将M₁的状态的子集{q₁}直接设计为接受状态，这是因为将{q₁}设计为M的接受状态并作为M的起始状态固然可以使M接受空串 ，但是也可能加进其他不想要的字符串。当存在某一q_i，如果δ₁ (q_i,a)＝q₁ 就会出现这种情况。增加接受状态ｑ₀，并且令转移函数为δ(ｑ₀,a) ＝{δ₁ (q₁,a)}（使ｑ₀发挥了的q₁计算功能），这保证了在M的状态图中ｑ₀只有射出的箭头，而没有射入的箭头，从而排除了ｑ₀接受除空串 外的其他字符串的可能性。

证明：设DFA M₁识别A，其中

M₁＝（Q₁，Σ，δ₁，ｑ₁，F₁）

构造识别A^*的DFA M，这里M ＝（Q，Σ，δ，ｑ，F）。

1) Q ＝（P（Q₁）－{φ}）∪{ｑ₀}

2) 字母表Σ与M₁ 的相同。

3) 转移函数δ定义如下：对于每一个状态Q_i∈（P（Q₁）－{φ}）∪{ｑ₀}和每一个a∈Σ，令

δ(ｑ₀,a) ＝{δ₁ (q₁,a)}

δ(Q_i,a)＝{q_i+1:q_i+1＝δ₁ (q_i,a)，q_i∈Q_i }若﹁ x（x∈Q_i∧x∈F₁）；

或＝{q_i+1:q_i+1＝δ₁ (q_i,a)，q_i∈Q_i }∪{δ₁ (q₁,a)}若﹁ x（x∈Q_i∧x∈F₁）.

4)q＝ｑ₀

5)F＝{Q_j: Q_j∈P(Q₁)∧ x(x∈Q_j∧x∈F₁}∪{ｑ₀}.

由M的构造，不难验证：对任一字符串ｗ₁ｗ₂…ｗ_n，如果ｗ₁ｗ₂…ｗ_n∈A^*，当且仅当M接受ｗ₁ｗ₂…ｗ_n。

在以上两定理的构造性证明中，都可将状态集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月）