文章目录
一、确定性有限自动机的接受问题
二、证明 "确定性有限自动机的接受问题" 可判定性
一、确定性有限自动机的接受问题
确定性有限自动机 的 接受问题 , 首先将 计算问题 转化为 语言 ,
因此得到如下 确定性有限自动机 语言 :
A D F A = { < B , w > : B 是 确 定 性 有 限 自 动 机 , 接 受 w 字 符 串 } \rm A_{DFA} = \{ <B, w> : B \ 是 \ 确定性有限自动机 , 接受 w 字符串 \}
A
DFA
={<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
;
二、证明 “确定性有限自动机的接受问题” 可判定性
证明上述计算问题是可判定的 ,
需要 构造一个图灵机 , 认识该语言 , 并且该图灵机一定是判定机 , 即可证明计算问题是可判定的 ;
构造图灵机 M \rm MM , 输入 < B , w > \rm <B, w><B,w> 字符串 , 即输入确定性有限自动机 B \rm BB 所能接受的字符串 w \rm ww ,
引入 丘奇-图灵命题 ,
没有必要设计图灵机 , 这里只需要设计算法即可 , 根据 丘奇-图灵命题 , 任何算法都对应一个图灵机 ,
这样就避免了设计一个图灵机 , 这个很复杂的过程 ;
证明过程 :
① 模仿 : 给定输入字符串 w \rm ww 之后 , 模仿 确定性有限自动机 B \rm BB 在 w \rm ww 字符串上进行计算 ;
② 接受 / 拒绝 : 如果上述计算进入接受状态 , 就让 图灵机 M \rm MM 接受 , 否则就让 图灵机 M \rm MM 拒绝 ;
确定性有限自动机 B \rm BB 在任何输入字符串 w \rm ww 上计算 , 一定会停机 , 即 在 字符串 w \rm ww 读取完毕的那一时刻 , 自动机就会停机 , 此时一定会出现一个 接受状态 或 拒绝状态 ;
上述自动机会停机 , 图灵机 M \rm MM 模仿该自动机进行计算 , 也会相应的进行停机 , 肯定能得到一个 接受 / 拒绝 的结果 , 因此 图灵机 M \rm MM 肯定是一个判定机 ;
因此 确定性有限自动机的接受问题 , 是可判定的 ;
问题不重要 , 重要的是理解证明问题的思路 , 过程 ;
