2、正则语言练习

5.7 设B是{0，1}上所有无限序列的集合。用对角化方法证明B是不可数的。

证明：为证明B是不可数的，必须证明在B和N之间不存在对应。下面用反证法证之。假设在B和N之间存在对应f，现在的任务是证明它没有应有的性质。因为它是一个对应，必须能将N的所有元素与B的所有元素进行配对。如果能找到B中的一个x，它和N中的任何元素都不能配对，则找到了矛盾。

为此，实际构造出这样一个x。方法如下：在选择它的每一位数字时，都使得：x不同于某个无

限序列，且此无限序列已与N中的一个元素配对。这样就能保证x不同于任何已配对的无限序列。

用一个例子来说明这个思路。假设对应f存在，且设f(1) = 010101…，f(2) = 101010…，f(3) =…

等等。则f将1和010101…配对，将2和101010…配对，依此类推。

要保证对每个n都有x ≠ f(n)。为保证x ≠ f(1)，只要保证x的第一位数字不同于f(1) =

010101…的第一位数字，即不是数字0，令它为1。为保证x ≠ f(2)，只要保证x的第二位数字不同于f(2) = 101010…的第一位数字，即不是数字0，令它为1。以这种方法继续下去，就能够得到x的所有数字。不难知道，对任意n，x都不是f(n)，因为x与f(n)在第n位上不同。

5.8 设T = {（i，j，k）| i，j，k ∈N}。证明T是可数的。

证明：先列出T的所有元素；然后将此序列中的第一个元素与N中的1配对，将第二个元素与2配对，依此类推。

设i = j = k = 1，T的元素为1个 （1，1，1）

设i = j = k = 2，T的元素为8个

（1，1，1）、（1，1，2）、（1，2，1）、（1，2，2） （2，1，1）、（2，1，2）、（2，2，1）、（2，2，2） 设i = j = k = 3，T的元素为27个

……。

按此顺序排列元素。第一种情况只包含一个元素（1，1，1），第二种情况包含8个元素，忽略重复的元素。所以此序列的前八个元素是（1，1，1）、（1，1，2）、（1，2，1）、（1，2，2）、（2，1，1）、（2，1，2）、（2，2，1）、（2，2，2）。以这种方法继续下去，就得到T的所有元素的一个序列。

5.9 回忆5.10定义中定义“集合有相同规模”的方法。证明“有相同规模”是一个等价关系。 证明：根据定义：称A和B有相同的规模，如果存在一对一且到上的函数f：A→B。既是一对一又

33

是到上的函数称为对应。在对应中，A的每个元素映射到B的唯一一个元素，且B的每个元素都有A的唯一一个元素映射到它。 设“有相同规模”为二元关系R。

1) R是自反的，即对每一个集合A，显然A和A有相同的规模，即ARA。

2) R是对称的，即对每一个集合A和B，如果ARB，即A和B有相同的规模，显然B和A也有

相同的规模，即BRA。

3) R是传递的，即对每一个集合A，B和C，如果ARB且BRC，即A和B有相同的规模，B和C

有相同的规模，显然A和C也有相同的规模，即ARC。

9.正则语言类在连结运算下封闭。

证明：设N1=(Q1,∑,δ1,q1,F1)识别A1，N2=(Q2,∑,δ2,q2,F2)识别A2， 构造识别A1· A2的N，这里N＝(Q，∑，δ，q1， F2)。

1) Q＝Q1∪Q2。

2) N的起始状态是N1的起始状态q1 。 3) N的接受状态集是N2的接受状态集F2。

4) 定义δ如下：对每一个q∈Q和每一个a∈∑ε，令

??1(q,a), 若q?Q1且q?F1? ????1(q,a), 若q?F1且a????(q,a)??? ?(q,a) {q}, 若q?F且a??21?1? ????2(q,a), 若q?Q2?

34