另一半是不可判定的 ;
下推自动机 ( PDA ) 可判定问题 :
① 下推自动机 ( PDA ) 的 接受问题 是可以判定的 ,
\rm A_{PDA}
可判定 ;
② 下推自动机 ( PDA ) 所 认识的语言是否是空集问题..., 是可判定的 ,
\rm E_{PDA}
可判定 ;
③ 任何一个 上下文无关语言 ( CFL ) 都是可判定语言 ;
下推自动机 ( PDA ) 不可判定问题 :
① 两个 下推自动机 ( PDA...) 是否相互等价 是不可判定的 ,
\rm EQ_{PDA}
可判定 ;
② 上下文无关语法 ( CFG ) 是否有歧义 , 不可判定 ;
二、概览
----
可计算性对应的模型就是 图灵机 ;...主要目的是 了解什么是计算 ,
计算理论分为 形式语言与自动机 , 可计算部分 , 计算复杂性部分 ;
之前博客中介绍的 自动机 , 确定性有限自动机 , 非确定性有限自动机 , 正则语言 , 泵引理..., 上下文无关语法 , 下推自动机 , 都属于 形式语言 与 自动机 部分 ;
现在开始讲解 可计算部分 , 即 图灵机 ;
图灵机内容分为 : 图灵机 , 图灵机变形 , 丘奇-图灵论题 ;
前几篇博客讲解的是