5、可判定性练习

1、.第5章、可判定性习题解答 练习5.1 对于下图所示的DFA M，回答下列问题，并说明理由。1010，10a. ADFA？是，M接受0100。b. ADFA？否，M不接受011。c. ADFA？否，不是ADFA的有效输入编码。d. AREX？是，DFA和正则表达式等价。e. EDFA？否，M接受串0100。f. EQDFA？是，L(M) = L(M)5.2考虑DFA和正则表达式是否等价的问题。将这个问题表示为一个语言并证明它可判定。解：设EQD-R=|A是DFA，B是正则表达式，L(A)=L(B)。构造如下TM F，F=“对于输入 , A是DFA，B是正则表达式，1) 将正则表达式B转化为等价

2、的DFA C。2) 判定EQDFA（EQDFA可判定）。3) 若接受，则接受；若拒绝，则拒绝。”F判定EQD-R。5.3 设ALLDFA= | A是一个识别S*的DFA。证明ALLDFA可判定。证明：设计一个判定ALLDFA的TM M即可。M“对于输入，其中A是一个DFA:1) 构造DFA B，使得L(B)= S*。2) 判定EQDFA（EQDFA可判定）。3) 若接受，则接受；若拒绝，则拒绝。”5.4 ACFG= | G是一个派生e 的CFG。证明ACFG可判定。证明：设计一个判定ACFG的TM M即可。M=“输入，G是一个CFG，1) 判定ACFG（ACFG可判定）。2) 若接受，则接受；

3、若拒绝，则拒绝。”5.5 设INFINITEDFA=|A是一个DFA，且L(A)是一个无限语言。证明INFINITEDFA是可判定的。证明：设计一个判定INFINITEDFA的TM M即可。 M=“对于输入，其中A是一个DFA：1) 按照引理2.32 证明中的构造方法，把DFA A转换成等价的正则表达式。2) 扫描正则表达式，如果包含星号运算符*，则接受；否则拒绝。”。5.6 设X是集合1，2，3，4，5，Y是集合6，7，8，9，10。以表5-4描述函数f：XY，g：XY。Nf(n)g(n)1610279368477566a. f 不是一对一的。因为13，但是f(1) = f(3) = 6。g

4、是一对一的。b. f 不是到上的。因为8Y，不存在aX，使得f(a) = 8。g是到上的。c. f 不是对应的。g是对应的。5.7 设B是0，1上所有无限序列的集合。用对角化方法证明B是不可数的。证明：为证明B是不可数的，必须证明在B和N之间不存在对应。下面用反证法证之。假设在B和N之间存在对应f，现在的任务是证明它没有应有的性质。因为它是一个对应，必须能将N的所有元素与B的所有元素进行配对。如果能找到B中的一个x，它和N中的任何元素都不能配对，则找到了矛盾。为此，实际构造出这样一个x。方法如下：在选择它的每一位数字时，都使得：x不同于某个无限序列，且此无限序列已与N中的一个元素配对。这样就能

5、保证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

6、= （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）、（

7、1，2，2）、（2，1，1）、（2，1，2）、（2，2，1）、（2，2，2）。以这种方法继续下去，就得到T的所有元素的一个序列。5.9 回忆5.10定义中定义“集合有相同规模”的方法。证明“有相同规模”是一个等价关系。证明：根据定义：称A和B有相同的规模，如果存在一对一且到上的函数f：AB。既是一对一又是到上的函数称为对应。在对应中，A的每个元素映射到B的唯一一个元素，且B的每个元素都有A的唯一一个元素映射到它。设“有相同规模”为二元关系R。1) R是自反的，即对每一个集合A，显然A和A有相同的规模，即ARA。2) R是对称的，即对每一个集合A和B，如果ARB，即A和B有相同的规模，显然B和A

8、也有相同的规模，即BRA。3) R是传递的，即对每一个集合A，B和C，如果ARB且BRC，即A和B有相同的规模，B和C有相同的规模，显然A和C也有相同的规模，即ARC。渺渺红尘，茫茫人海，没有过早，也没有太晚，遇见的自然是恰逢其时。有人说，这世间的所有相遇，都是久别重逢。惟有父母与子女，是为了别离。父母为自己付出的，永远是百分之百的绵绵恒爱。每当看到满头如雪，弯腰驼背，步履蹒跚的父亲母亲，总会不由自主地想起，他们曾用最纯朴、最勤劳的方式为自己撑起过一片天，现如今却是衰老伴着他们走过一年又一年。于父母眼里，自己就像飘在天空的风筝，无论飞得多高多远，他们也舍不得松开牵挂的那根线。这种深厚的爱，若高山阔海，就算用一辈子的时间，恐怕也回馈不完 .想来那句：你养我长大，我陪你变老，应是最好的报答。记得一首友情的歌，里面那段歌词格外打动人：友情，人人都需要友情，不能孤独，踏上人生的旅程听完，特别想感谢那些出现在自己不同人生阶段的朋友，感谢这一路上你们给予的支持和鼓励。此生何其幸运，能成为彼此的亲密挚友。除了家人，最熟悉我的还有你童年，一起玩耍嬉戏；少年，一起努力学习；青年，互相聆听各自的小秘密；愿中年的彼此，都能好好保重自己；愿我们老的时候还能一起喝茶、一起聊聊不太完美的却又共同参与过的往昔。人