ITOC chapter4 可判定性

4 Decidability 可判定性

4.1 Decidable Languages 可判定语言

4.1.1 正则语言的可判定性问题
acceptance problem for DFA DFA接受问题

问能否检测一个确定性有穷自动机B是否接受一个串w
ADFA={⟨B,w⟩| B是DFA,w是串,B接受w}.
问能否检测一个有穷自动机B是否接受一个串w等同于问<B,w>是否是语言ADFA的元素。若ADFA可判定,则可检测。
证明思路:设计一个判定ADFA的TM M。
M:对于输入<B,w>,模拟B运行,输入w。若模拟返回接受状态,则接受,若以非接受状态(拒绝/循环)结束,则拒绝。

acceptance problem for NFA NFA接受问题

问能否检测一个非确定性有穷自动机B是否接受一个串w

ANFA={⟨B,w⟩|B是NFA,w是串,B接受w}.

证明思路:将NFA转换为DFA,再用上面的思路走一遍即可

acceptance problem for REX REX接受问题

问能否检测一个正则表达式是否派生一个给定的串。

AREX={⟨B,w⟩|B是正则表达式,w是串,B派生w}.

证明思路,将B转换为DFA,再用上面的思路走。

综上三点,对于可判定性,DFA、NFA与正则表达式对TM都是等价的,因为TM能将他们互相转换。

emptiness testing for DFA DFA空性质测试

问能否检测一个确定性有穷自动机A是否不接受任何串。

EDFA={⟨A⟩| A是一个DFA且 L(A)=∅}.

whether two DFAs recognize the same language DFA同识问题

问能否检测俩DFA是否识别同一个语言。

EQDFA={⟨A,B⟩| A,B都是DFA且L(A)=L(B)}.

4.1.2 与上下文无关语言的可判定性问题
acceptance problem for CFG CFG接受问题

问能否检测某个CFG是否派生一个特定的串w。

ACFG={⟨G,w⟩}| G是一个CFG,w是串,G派生w }.

emptiness testing for CFG CFG空性质测试

问能否检测某个CFG是否不派生任何串

ECFG={⟨G⟩| G是一个CFG且L(G)=∅}.

whether two CFGs generate the same language CFG同识问题

能否检测俩CFG是否派生出相同的语言

EQCFG={⟨G,H⟩| G和H是CFG且L(G)=L(H)}.

这是不可判定的。

every context-free language is decidable CFL可判定性

每个上下文无关语言都可以用图灵机来判定:

MG = “对于输入w:
1. 在输入<G,w>上运行TM S(S是上面判定ACFG的TM).
2. 如果这个机器接受,则接受,否则拒绝。”

4.2 Undecidability 停机问题

图灵机的能力是有限的,有些问题是算法上不可解的。如:

能否检测一台图灵机是否接受给定的串

4.2.1 THE DIAGONALIZATION METHOD 对角线法

如果两个集合之间存在一个双射函数使其一一对应,那么两个集合大小相等。
比如偶数集与自然数集、直线与平面,局部与整体“等大”。

可数(countable)的概念–我们可以在被数的对象与自然数集N之间建立一一对应关系,如证明有理数集Q可数

一行行考虑不行,就从对角线去看:第一条对角线由一个1/1,第二条2/1和1/2,按这个顺序把不重复的项一一加入队列中,就得到一个序列,这个序列显然是可数的。

证明实数集R不可数

证明思路:

反证法,假设R与N之间存在双射函数f(n),那么我们只要找到反例,即在值域之外的实数即可。

反例:小数点后第i位与f(i)的的小数点后第i位不同。

由此我们可以知道有些语言是不可判定的,因为有可数个图灵机,但有不可数个语言。而一个图灵机只能识别一个语言,所以必定存在语言不能被任何图灵机所识别。

说明“有可数个图灵机“:首先,对任意字母表,其上所有串的集合是可数的,因为,对于自然数n,长度为n的串只有有限多个,而每个图灵机对应一个编码,所以由所有图灵机构成的集合也是可数的。

说明“有不可数个语言“:首先,无限二进制序列B(由0和1构成的无限序列)是不可数的,

Σ*是0,1所有可能二进制序列集合,A是0开头的二进制序列集合,XA是特征序列(Σ*和A同时有则1)

XA对应B是一一对应关系,B是不可数的,所以语言的个数也是不可数的。

4.2.2 AN UNDECIDABLE LANGUAGE 停机问题是不可判定的

能否检测一台图灵机是否接受给定的串

ATM={⟨M,w⟩| M是一台TM,w是串,M接受w }

先证一下ATM是可被图灵识别的:
只需构造:

U = “对于输入<M,w>:
1. 对输入w模拟M.
2. 如果M进入接受状态,则接受,如果M进入拒绝状态,则拒绝”

不能判定的原因:M可以对输入w产生循环,如果M知道自己不停机,他能拒绝w,但实际上他无法知道。

反证法开擼:假设ATM是可判定的,设H是ATM的判定器,那么对于输入<M,w>如果M接受w,H就停机且接受w,如果M拒绝或循环,H也会停机且拒绝w。

我们构造一个新的图灵机D,以H作为子程序,输入M与M的描述,输出与H相反的结论,即:对于输入<M,<M>>,模拟运行H,若H接受则拒绝,若H拒绝则接受。那么我们得到了一个D(<M>),如果M不接受<M>,输出接受,如果M接受<M>,输出拒绝。

那么我们以D的描述<D>作为输入运行D时,就会出现:如果D不接受<D>,输出接受。这是一个矛盾。所以假设和设计的TM H、D都不存在。证毕。

蕴含的对角线法:

 

 

4.2.3 A TURING-UNRECOGNIZABLE LANGUAGE 一个图灵不可识别的语言

上面说了,ATM不可判定,但可识别,但有些语言甚至识别都不行。

定理:一个语言是可判定的当且仅当它和它的补语言都是图灵可识别的。

1.判定–>识别

A是可判定的,当然可识别,A的补显然也是可识别的。

2.识别–>判定

A和A补都是可识别的,那么令M1是A的识别器,M2是A补的识别器。构造判定器M:

M = “对于输入w:
1. 对于输入w双带并行运行M1和M2.
2. 如果M1接受,则接受,如果M2接受,则拒绝”

因为一个输入要么在A中,要么在A补中,所以M总会停机,并且能做到接受所有在A中串,拒绝所有不在A中的串,所以M就是A的判定器。

推论:ATM补不是图灵可识别的。

因为ATM是图灵可识别的,如果ATM补也是可识别的,根据上述定理,ATM是可判定的。但前面又证明了不可判定,所以ATM补不是图灵可识别的,其他也可以类似套路,666。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注