计算机理论导引第三版答案第四章,《计算理论导引》第四
章：可判定性-学习笔记诟屍...
第四章：可判定性
4 Decidability
关于其他章节的内容，请点这：《计算理论导引》学习笔记
4.1 Decidable Languages
⼏个可判定的语⾔
acceptance problem for DFA
the acceptane problem for DFAs of testing whether a particular deterministic finite automaton accepts a given string can be expressed as a language\( A_{DFA}\).
\( A_{DFA} = \{\langle B,w \rangle | \text{ B is a DFA that accepts input string w}\}\).
is a member of The problem of testing whether a DFA B accepts an input w is the same as the problem of testing whether is a member of the language \( A_{DFA}\).
We simply need to present a TM M that decides \( A_{DFA}\).
, where B is a DFA and w is string:
M = “on input , where B is a DFA and w is string:
1. Simulate B on input w.
2. If the simulation ends in an accept state, accept. If it ends in a nonaccepting state, reject.”
acceptance problem for NFA
\( A_{NFA} = \{\langle B,w \rangle | \text{ B is a NFA that accepts input string w}\}\).
, where B is a NFA and w is string:
N = “on input , where B is a NFA and w is string:
1. Convert NFA B to an equivalent DFA C.
2. Run TM M on input .
2. If M accepts, accept; otherwise, reject.”
acceptance problem for REX
\( A_{REX} = \{\langle B,w \rangle | \text{ B is a regular expression that generates string w}\}\).
P = “On input , where R is a regular expression and w is a string:
1. Convert regular expression R to an equivalent NFA A.
2. Run TM N on input .
3. If N accepts, accept; if N rejects, reject.”
emptiness testing for DFA
\( E_{DFA} = \{\langle A \rangle | \text{ A is a DFA and } L(A) = \emptyset\}\).
T = “On input , where A is a DFA:
1. Mark the start state of A.
2. Repeat until no new states get marked:
3. Mark any state that has a transition coming ino it from any state that is already marked.
4. If no accept state is marked, accept; otherwise, reject.”
whether two DFAs recognize the same language
\( EQ_{DFA} = \{\langle A,B \rangle | \text{ A and B are DFA and } L(A) = L(B)\}\).
\( L(C) = (L(A) \cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B))\).
We can construct C form A and B with the sonstructions for proving the class of regular languages closed under complementation, union, and intersection.
\( L(C) = \emptyset \iff L(A) = L(B)\).
F = “On input , where A and B are DFAs:
1. Condtruct DFA C as described.
2. Run TM T on input .
3. If T accepts, accept. If T rejects, reject.”
acceptance problem for CFG
\( A_{CFG} = \{\langle G,w \rangle\} | \text{ G is a CFG that generates string w }\}\).
直接枚举会得到recognizer⽽不是decider
If G were in Chomsky normal form, any derivation of w has 2n-1 steps, where n is the length of w.
In that case, checking only derivations with 2n-1 steps to determine whether G generates w would be sufficient.
S = “on input , where G is a CFG and w is a string:
1. Convert G to an equivalent grammar in Chomsky normal form.
2. List all derivations with 2n-1 steps, where n is the length of w; except if n = 0, then instead list all derivations with one step.
3. If any of these deravation generate w, accept; if not, reject.”
emptiness testing for CFG
\( E_{CFG} = \{\langle G \rangle | \text{ G is a CFG and } L(G) = \emptyset\}\).
转化为可达性问题，⽬的地是terminal symbols，起点是start variable
R = “On input , where G is a CFG:
1. Mark all terminal symbols in G.
2. Repeat until no new variables get marked:
3. Mark any variable A where G has a rule \( A \longrightarrow U_1U_2\dots U_k\) and each symbol \( U_1,\dots,U_k\) has already been marked.
4. If the start variable is not marked, accept; otherwise, reject.
whether two CFGs generate the same language
\( EQ_{CFG} = \{\langle G,H \rangle | \text{ G and H are CFGs and } L(G) = L(H)\}\).
在这⾥，\( EQ_{DFA}\)的套路⽤不了了
因为，The class of context-free languages is not closed under complementation or intersection.(Exercise 2.2)
事实上，这是不可判定的
every context-free language is decidable
\( M_G\) = “On input w:
1. Run TM S on input .
2. If this machine accepts, accepts, if it rejects, reject.”
relationship-among-classes-of-languages 4.2 Undecidability
对⾓线法
接下来讲了⼀波⽆穷⼤集合之间怎么⽐较⼤⼩，就是为了引⼊对⾓线法？
简单的说，如果两个集合之间存在⼀个双射函数使其⼀⼀对应，那么两个集合⼤⼩相等 ⽐如偶数集与⾃然数集、直线与平⾯ ，局部与整体等⼤，是不是很神奇，这就是⽆穷⼤的魅⼒
在这基础上定义了可数(countable)这个概念：
A set A is countable if either it is finite or it has the same size as N.
我们⽇常在数数(count)的时候“1，2，3，。。。”其实就是在被数的对象与⾃然数集N之间建⽴⼀⼀对应关系
于是按⼀个套路把有理数排列起来后，发现可以⼀个不漏地数下去，就证明有理数可数了 很⾃然地，我们会想，⽆理数呢？实数呢？复数呢？
很遗憾，这些都是不可数的，这时就要⽤对⾓线法证明了
反证法：
假设R与N之间存在双射函数f(n)
那么我们可以构造出⼀个不在f(n)值域的实数出来，这就破坏假设了，证毕。
这个数是这样的：
⼩数点后第i位与f(i)的的⼩数点后第i位不同，如图
diagonalization-R
这个数的每⼀位都和对⾓线上对应位不同，所以叫对⾓线法。
很容易证明，代数数是可数的，⽽复数是不可数的，复数⼜由代数数与超越数组成
于是就证明了超越数的存在性，却没证明⼀个数是超越数，康托尔就是迪奥
所以必定存在some languages are not Turing-recognizalbe
⼀个不可判定的语⾔
\( A_{TM} = \{\langle M,w \rangle | \text{ M is a TM and M accepts w }\}\) is undecidable.
不妨先证⼀下\( A_{TM}\)是可被图灵识别的：
只需构造⼀个图灵机出来就可以了：
U = “On input , where M is a TM and w is a string:
1. Simulate M on input w.
2. If M ever enters its accept state, accept; if M ever enters its reject state, reject.”
不可判定的证明：
(还有个更简洁的证明在第六章)
假设\( A_{TM}\)是可判定的 \( \longrightarrow\) 存在decider H \( \longrightarrow\) 存在decider D \( \longrightarrow\) 存在悖论
所以假设不成⽴，证毕。acceptlanguage
其中，
H就是\( A_{TM}\)的decider
\( H(\langle M,w \rangle) =
\begin{cases}
accept & \text{if M accepts w} \\
reject & \text{if M does not accept w}
\end{cases}\)
D = “On input , where M is a TM:
1. Run H on input >.
2. Output the opposite of what H outputs. That is, if H accepts, reject; and if H rejects, accept.”
\( D(\langle M \rangle) =
\begin{cases}
accept & \text{if M does not accepts }\langle M \rangle \\
reject & \text{if M accepts }\langle M \rangle
\end{cases}\)
是不是很像“理发师悖论”？所以接下来：
\( D(\langle D \rangle) =
\begin{cases}
accept & \text{if D does not accepts }\langle D \rangle \\
reject & \text{if D accepts }\langle D \rangle
\end{cases}\)
当对D输⼊的时候,D既不可以accept，⼜不可以reject，也不可以其他，所以⽭盾出现。
是不是感觉没⽤对⾓线法？其实⼈家⽤了，你看不出来⽽已，有图有真相：
diagonalization-TM 另外，有个问题：
如果D⾥⾯不运⾏H，⽽是运⾏U，好像也有⽭盾啊，那不就证明了U不存在？
这个问题我纠结了⼏个钟ORZ。。。最后我的答案是这样的：(欢迎到评论区和我讨论)
⾸先明确D修改后是这样的：
E = “On input , where M is a TM:
1. Run U on input >.
2. If U ever enters its accept state, reject; if U ever enters its reject state, accept.”
也就是说，与D不同的是，E有可能会死循环，这就是关键
现在再对E输⼊看看：
同样，E既不可以accept，⼜不可以reject
但是，现在E可以死循环，所以我的结论是：E()会死循环
所以E并不像D那样是⼀个⽭盾的不可能存在的图灵机，答毕。
定理4.0
A language is decidable iff it is Turing-recognizable and co-Turing-recognizable.
(We say that a language is co-Turing-recognizable if it is the complement of a Turing-recognizable language.)
证明很简单，略去
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议