发布时间 : 2024/6/29 7:39:57 星期六 文章计算理论更新完毕开始阅读

5. 给定图灵机是否接受空串？

设两个语言：L1= {M|M(e)停机}；H = {|M(w)停机}已知H不可判定，只需要找到H->L1的归约即可。令f(“M”,“w”) =M’(y) = “M(w)”, M’ 输入任何y的输出都是M在w上的模拟结果（获得的具体做法是删除任何输入，写入w，再在w上模拟M）。则{“M”,”w“}∈H，iffM’ 在任何串上停机，iff M’在空串停机 M‘∈L1。

6. ①给定TM M，是否存在在M上停机的串？ ②给定TM M， M是否在所有上停机的串？

设L = {M|M(a) where a∈Σ*} ，H = {|M(w)停机}。寻找H到L的归约。令f(“M”,“w”) =M’(y) = “M(w)”, M’ 输入任何y输出都是M在w上的模拟结果（获得的具体做法是删除任何输入，写入w，再在w上模拟M）。{“M”,”w“}∈H，iffM’ 在任何串上停机，iff M’在任何串上停机，iff M’在所有a上停机(a∈Σ*), i.e. M’∈L。

7. 给定TM M，is L(M) finite?

设Finite = {L(M) where L(M) isfinite}; AH = {|M accept w}存在从AH（非递归）到﹁Finite的递归函数f，f(“M”,“w”)=M’(y) = “M(w)”, 显然f可计算。则{M,w}∈AH iff M halts on w iff M’ accept any y∈Σ*ifff(M,w) is infinite, i.e. M’∈ ﹁Finite。由于AH归约到﹁Finite，所以﹁Finite非确定，又∵确定性在补下封闭，所以Finite也是非确定的。

8. 给定TM M, 带上是否出现过a（a∈Σ）？

设Write_a = {|M有一条在带上写a的规则}；AH = {|M accept w} 存在从AH（非递归）到﹁Finite的递归函数f，f(“M”,“w”)=M’(“T”,”a”) = Simulate M(w).

若M接受w，在带上写a；否则什么也不写。则{M,w}∈AH iffM halts on w iffM’在带上写了一个aiff f(“M”,“w”)∈Write_a. 所以Write_a非确定。

9. 给定M1，M2，它们是否在一个相同串上停机？

设2Halts = {|存在令他们都停机的串w}；H = {|M(w)停机}构造新机器M’，在M’带上写w，模拟M1若停机则清空带，写w，再模拟M2，若M2在w上也停机，则M’停机。则有M’停机iff∈2Halt iff∈H且∈H。

10. 给定M，只要M接受w，M就接受wR

设S = {M| M accepts wRwhenever it accept w}; AH = {|M acceptw}

递归函数f定义如下，f(M,w)= M’(y), 在M’上模拟M(w).

当M接受w时，create M’ 只接受串1111；当M拒绝w时，create M’只接受串01。 则∈AH iff M接受w iff M’只接受1111 iffM’∈S，类似的?AHiffM’接

受01不接受10iffM’?S

判定语言Recursive/Recursive Enumerable / Not R.e.

1. L1 = {M| there exists an input on which M haltsin less than || steps}

R.

Test on all w less than |M| 2. L2 = {M| |L(M)|<4} Not R.e. a) Reductionfrom H , 说明是R.e.或非R.e. b) ∈非H，当且仅当M’属于L2

3. L3 = {M| |L(M)|>2} R.e. not R

Textbook Summary

1. 与自然数集合N等势的集合是可数无穷的，称有穷的or可数无穷的集合是可数的。非可数的集合称作不可数的。

2. DFA( K, Σ, s, F, δ )；NFA（K,Σ，s，F，Δ）

3. 每台NFA都有一台等价的DFA（method:find closure）

4. 有穷自动机接受的语言类= 正则语言类（正则表达式描述的语言类） 5. 正则语言在各种运算下封闭

6. 语言是正则的，iff其等价语言中有有穷个等价类。 7. DFA状态最小化->寻找等价类（初始等价类F& K-F） 8. CFL（V，Σ，R，S） 9. 存在非正则的CFL

10. 能够生成>=两棵语法分析树的字符串的文法叫做歧义的。 11. PDAM=（K，Σ，Γ，Δ，s，F），Γ为栈符号 12. PDA接受的语言正好是CFL

13. 正则语言（xynz）和CFL（uvnxynz）的泵定理

14. L={anbn}∈CFL，L={anbncn}?CFL但是是递归的，L={an,n为素数}不是CFL

15. Chomsky范式（CNF）：若Rí(V-Σ)×V2，则称G=（V，Σ，R，S）为Chomsky范式

16. 有穷自动机总是停机。 17. CFG到CNF的转化： 1) 消除长rules

2) 消除空rules（A->e） 3) 消除短rules（A->aor A->B）

18. 对任意CFLG，都可以在多项式时间构造Chomsky范式G’,使得L(G’)=L(G)-(Σ∪{e})

19. 没有chomsky范式能够表示length<2的字符串，所以包含<2的字符串的语言不能转化到chomsky范式。

20. 确定型CFL（确定型PDA接受的语言类）在补下封闭。 21. TM(K，Σ，δ，s，H)，注意字母表Σ不包含←和→ 22. 若存在TM判定L，则称L是递归的。

23. 如果对于所有w属于Σ*，M(w) = f(w)，我们说M计算函数f，若存在TM计算f，则f称为递归的。

24. 半判定语言的TM都不是算法

25. 多带、多带头、双向无穷带or多维带的TM，其判定or半判定的任何语言及任何函数，都分别可用标准TM判定、半判定or计算。

26. 非确定型TM：一个格局可在一步里产生多个其他格局，NDTM is no more powerful than original TM

27. 若非确定型TMM半判定或者判定语言L，或者计算函数f，则存在标准型TMM’