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

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

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

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

A N F A = { < B , w > : B   是   非 确 定 性 有 限 自 动 机 , 接 受 w 字 符 串 } \rm A_{NFA} = \{ : B \ 是 \ 非确定性有限自动机 , 接受 w 字符串 \} ANFA​={:B 是 非确定性有限自动机,接受w字符串}

w \rm w w 是字符串 ;

B \rm B B 是非确定性有限自动机 ;

B \rm B B 接受 w \rm w w ;

将 B \rm B B 非确定性有限自动机 所 接受的 字符串 w \rm w w 放在一个集合中 , 就得到了 非确定性有限自动机 B \rm B B 的语言 A D F A \rm A_{DFA} ADFA​ ;

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

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

规约过程 ( 证明思路 ) :

构造一个 判定机 ( 结果是 接受 / 拒绝 的 图灵机 ) N \rm N N , 判定机要求如下 :

判定机 N \rm N N , 输入 < B , w > \rm 字符串 , 即输入 非确定性有限自动机 B \rm B B 所能接受的字符串 w \rm w w ,

① 自动机转化 : 将 非确定性有限自动机 B \rm B B 转为等价的 确定性有限自动机 C \rm C C ;

② 规约过程 : 使用上一篇博客 【计算理论】可判定性 ( 确定性有限自动机的接受问题 | 证明 “确定性有限自动机的接受问题“ 的可判定性 ) 的算法判定转化之后的 确定性有限自动机 C \rm C C , 在输入字符串 w \rm w w 上计算 , 是否会停机 ;

• 模仿 : 构造图灵机 M \rm M M , 给定输入字符串 w \rm w w 之后 , 模仿 确定性有限自动机 C \rm C C 在 w \rm w w 字符串上进行计算 ;

• 接受 / 拒绝 : 如果上述计算进入接受状态 , 就让 图灵机 M \rm M M 接受 , 否则就让 图灵机 M \rm M M 拒绝 ;

③ 图灵机 N \rm N N 结果 : 如果上述 图灵机 M \rm M M 接受 , 则本次构造的 图灵机 N \rm N N 结果也是 接受 ; 如果上述 图灵机 M \rm M M 拒绝 , 则本次构造的 图灵机 N \rm N N 结果也是 拒绝 ;

构造 图灵机 M \rm M M 的过程 , 相当于一个子程序 ;