文章目录
一、非确定性有限自动机的接受问题
二、证明 "非确定性有限自动机的接受问题" 可判定性
一、非确定性有限自动机的接受问题
非确定性有限自动机 的 接受问题 , 首先将 计算问题 转化为 语言 ,
因此得到如下 非确定性有限自动机 语言 :
A N F A = { < B , w > : B 是 非 确 定 性 有 限 自 动 机 , 接 受 w 字 符 串 } \rm A_{NFA} = \{ <B, w> : B \ 是 \ 非确定性有限自动机 , 接受 w 字符串 \}
A
NFA
={<B,w>:B 是 非确定性有限自动机,接受w字符串}
w \rm ww 是字符串 ;
B \rm BB 是非确定性有限自动机 ;
B \rm BB 接受 w \rm ww ;
将 B \rm BB 非确定性有限自动机 所 接受的 字符串 w \rm ww 放在一个集合中 , 就得到了 非确定性有限自动机 B \rm BB 的语言 A D F A \rm A_{DFA}A
DFA
;
二、证明 “非确定性有限自动机的接受问题” 可判定性
任何 非确定性有限自动机 与 确定性有限自动机 是等价的 , 证明 “非确定性有限自动机的接受问题” 是可判定的 , 需要 规约 成 上一篇博客 【计算理论】可判定性 ( 确定性有限自动机的接受问题 | 证明 “确定性有限自动机的接受问题“ 的可判定性 ) 中证明的 “确定性有限自动机接受问题” 是可判定的 ;
规约过程 ( 证明思路 ) :
构造一个 判定机 ( 结果是 接受 / 拒绝 的 图灵机 ) N \rm NN , 判定机要求如下 :
判定机 N \rm NN , 输入 < B , w > \rm <B, w><B,w> 字符串 , 即输入 非确定性有限自动机 B \rm BB 所能接受的字符串 w \rm ww ,
① 自动机转化 : 将 非确定性有限自动机 B \rm BB 转为等价的 确定性有限自动机 C \rm CC ;
② 规约过程 : 使用上一篇博客 【计算理论】可判定性 ( 确定性有限自动机的接受问题 | 证明 “确定性有限自动机的接受问题“ 的可判定性 ) 的算法判定转化之后的 确定性有限自动机 C \rm CC , 在输入字符串 w \rm ww 上计算 , 是否会停机 ;
模仿 : 构造图灵机 M \rm MM , 给定输入字符串 w \rm ww 之后 , 模仿 确定性有限自动机 C \rm CC 在 w \rm ww 字符串上进行计算 ;
接受 / 拒绝 : 如果上述计算进入接受状态 , 就让 图灵机 M \rm MM 接受 , 否则就让 图灵机 M \rm MM 拒绝 ;
③ 图灵机 N \rm NN 结果 : 如果上述 图灵机 M \rm MM 接受 , 则本次构造的 图灵机 N \rm NN 结果也是 接受 ; 如果上述 图灵机 M \rm MM 拒绝 , 则本次构造的 图灵机 N \rm NN 结果也是 拒绝 ;
构造 图灵机 M \rm MM 的过程 , 相当于一个子程序 ;
