形式语言与自动机 , 可计算部分 , 计算复杂性部分 ;
形式语言与自动机 内容 : 自动机 , 确定性有限自动机 , 非确定性有限自动机 , 正则语言 , 泵引理 , 上下文无关语法 , 下推自动机..., 都属于 形式语言 与 自动机 部分 ;
可计算 内容 : 图灵机 , 确定性图灵机 , 非确定性图灵机 , 丘奇-图灵命题 , 可判定性 , 可计算性 等问题 ;
计算复杂性 内容 : 时间复杂性..., 模型间的时间复杂性关系 ,
\rm P
类 ,
\rm NP
类 ;
计算理论 知识点很枯燥 , 但是 在进行理论研究时 , 或者大的计算机工程实践时 , 很有用 ;
二、计算问题的判定性...----
根据计算模型 , 可以将判定性问题 , 总结成以下几点 :
① 所有 关于 图灵机 的计算问题 , 都是 不可判定的 ; ( 莱斯定理 )
② 所有 关于 确定性有限自动机 的计算问题 ,...\rm M
为什么必须是判定机 :
假设
\rm M
是图灵机 , 在某些输入上是不停机的 , 如输入字符串为
\rm aab
;
图灵机
\rm M
在
\rm aab
字符串上进行计算时