【计算理论】可判定性 ( 可判定性总结 )

文章目录

• 一、可判定性总结
• 二、概览

一、可判定性总结

---

确定性有限自动机 , 下推自动机 , 图灵机 是目前提到过的计算模型 ;

关于 确定性有限自动机 的所有计算问题都是 可判定的 ;

关于 图灵机 的所有计算问题 都是 不可判定的 ;

关于 下推自动机 的计算问题 , 一半是可以判定的 , 另一半是不可判定的 ;

下推自动机 ( PDA ) 可判定问题 :

① 下推自动机 ( PDA ) 的 接受问题 是可以判定的 ,

\rm A_{PDA}

可判定 ;

② 下推自动机 ( PDA ) 所 认识的语言是否是空集问题 , 是可判定的 ,

\rm E_{PDA}

可判定 ;

③ 任何一个 上下文无关语言 ( CFL ) 都是可判定语言 ;

下推自动机 ( PDA ) 不可判定问题 :

① 两个 下推自动机 ( PDA ) 是否相互等价 是不可判定的 ,

\rm EQ_{PDA}

可判定 ;

② 上下文无关语法 ( CFG ) 是否有歧义 , 不可判定 ;

二、概览

---

可计算性对应的模型就是 图灵机 ; 主要目的是 了解什么是计算 ,

计算理论分为 形式语言与自动机 , 可计算部分 , 计算复杂性部分 ;

之前博客中介绍的 自动机 , 确定性有限自动机 , 非确定性有限自动机 , 正则语言 , 泵引理 , 上下文无关语法 , 下推自动机 , 都属于 形式语言 与 自动机 部分 ;

现在开始讲解 可计算部分 , 即 图灵机 ;

图灵机内容分为 : 图灵机 , 图灵机变形 , 丘奇-图灵论题 ;

前几篇博客讲解的是 可计算部分 , 图灵机 , 确定性图灵机 , 非确定性图灵机 , 丘奇-图灵命题 , 可判定性 , 可计算性 等问题 ;