欢迎来到天天文库
浏览记录
ID：60811805
大小：42.00 KB
页数：5页
时间：2020-12-20
《可判定性练习.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章、可判定性习题解答练习5.1对于下图所示的DFAM，回答下列问题，并说明理由。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={
2、A是DFA，B是正则表达式，L
3、(A)=L(B)}。构造如下TMF，F=“对于输入,A是DFA，B是正则表达式，1)将正则表达式B转化为等价的DFAC。2)判定∈EQDFA（EQDFA可判定）。3)若接受，则接受；若拒绝，则拒绝。”F判定EQD-R。5.3设ALLDFA={
4、A是一个识别S*的DFA}。证明ALLDFA可判定。证明：设计一个判定ALLDFA的TMM即可。M＝“对于输入，其中A是一个DFA:1)构造DFAB，使得L(B)=S*。2)判定∈EQDFA（EQDFA可判定）。3)若接受，则接受；若拒绝，则拒绝。”5.4AεCFG=
5、{
6、G是一个派生e的CFG}。证明AεCFG可判定。证明：设计一个判定AεCFG的TMM即可。M=“输入，G是一个CFG，1)判定∈ACFG（ACFG可判定）。2)若接受，则接受；若拒绝，则拒绝。”5.5设INFINITEDFA={
7、A是一个DFA，且L(A)是一个无限语言}。证明INFINITEDFA是可判定的。证明：设计一个判定INFINITEDFA的TMM即可。 M=“对于输入，其中A是一个DFA：1)按照引理2.32证明中的构造方法，把DFAA转换成等价的正则表达式。2)扫描正则表达式，如果包含星号运
8、算符*，则接受；否则拒绝。”。5.6设X是集合{1，2，3，4，5}，Y是集合{6，7，8，9，10}。以表5-4描述函数f：X→Y，g：X→Y。Nf(n)g(n)1610279368477566a.f不是一对一的。因为1≠3，但是f(1)=f(3)=6。g是一对一的。b.f不是到上的。因为8∈Y，不存在a∈X，使得f(a)=8。g是到上的。c.f不是对应的。g是对应的。5.7设B是{0，1}上所有无限序列的集合。用对角化方法证明B是不可数的。证明：为证明B是不可数的，必须证明在B和N之间不存在对应。下面用反证法证之。假设在B和N之间存在对应f，现
9、在的任务是证明它没有应有的性质。因为它是一个对应，必须能将N的所有元素与B的所有元素进行配对。如果能找到B中的一个x，它和N中的任何元素都不能配对，则找到了矛盾。为此，实际构造出这样一个x。方法如下：在选择它的每一位数字时，都使得：x不同于某个无限序列，且此无限序列已与N中的一个元素配对。这样就能保证x不同于任何已配对的无限序列。用一个例子来说明这个思路。假设对应f存在，且设f(1)=…，f(2)=…，f(3)=…等等。则f将1和…配对，将2和…配对，依此类推。要保证对每个n都有x≠f(n)。为保证x≠f(1)，只要保证x的第一位数字不同于f(1)
10、=…的第一位数字，即不是数字0，令它为1。为保证x≠f(2)，只要保证x的第二位数字不同于f(2)=…的第一位数字，即不是数字0，令它为1。以这种方法继续下去，就能够得到x的所有数字。不难知道，对任意n，x都不是f(n)，因为x与f(n)在第n位上不同。5.8设T={（i，j，k）
11、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，
12、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有相同的规模，如果存在一对一且到上的
13、函数f：A→B。既是一对一又是到上的函数称为对应。在对应中，A的每个元素映射到B的唯一一个元素，且B的每个元素都有A的唯一
此文档下载收益归作者所有
