【计算理论】可判定性 ( 非确定性有限自动机的接受问题 | 证明 “非确定性有限自动机的接受问题“ 的可判定性 )

文章目录

• 一、非确定性有限自动机的接受问题
• 二、证明 "非确定性有限自动机的接受问题" 可判定性

一、非确定性有限自动机的接受问题

非确定性有限自动机 的 接受问题 , 首先将 计算问题 转化为 语言 ,

因此得到如下 非确定性有限自动机 语言 :

是字符串 ;

是非确定性有限自动机 ;

接受

;

将

非确定性有限自动机 所 接受的 字符串

放在一个集合中 , 就得到了 非确定性有限自动机

的语言

;

二、证明 “非确定性有限自动机的接受问题” 可判定性

任何 非确定性有限自动机 与 确定性有限自动机 是等价的 , 证明 “非确定性有限自动机的接受问题” 是可判定的 , 需要 规约 成 上一篇博客 【计算理论】可判定性 ( 确定性有限自动机的接受问题 | 证明 “确定性有限自动机的接受问题“ 的可判定性 ) 中证明的 “确定性有限自动机接受问题” 是可判定的 ;

规约过程 ( 证明思路 ) :

构造一个 判定机 ( 结果是 接受 / 拒绝 的 图灵机 )

, 判定机要求如下 :

判定机

, 输入

字符串 , 即输入 非确定性有限自动机

所能接受的字符串

,

① 自动机转化 : 将 非确定性有限自动机

转为等价的 确定性有限自动机

;

② 规约过程 : 使用上一篇博客 【计算理论】可判定性 ( 确定性有限自动机的接受问题 | 证明 “确定性有限自动机的接受问题“ 的可判定性 ) 的算法判定转化之后的 确定性有限自动机

, 在输入字符串

上计算 , 是否会停机 ;

• 模仿 : 构造图灵机

, 给定输入字符串

之后 , 模仿 确定性有限自动机

在

字符串上进行计算 ;

• 接受 / 拒绝 : 如果上述计算进入接受状态 , 就让 图灵机

接受 , 否则就让 图灵机

拒绝 ;

③ 图灵机

结果 : 如果上述 图灵机

接受 , 则本次构造的 图灵机

结果也是 接受 ; 如果上述 图灵机

拒绝 , 则本次构造的 图灵机

结果也是 拒绝 ;

构造 图灵机

的过程 , 相当于一个子程序 ;