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

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

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

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

A D F A = { < B , w > : B   是   确 定 性 有 限 自 动 机 , 接 受 w 字 符 串 } \rm A_{DFA} = \{ : B \ 是 \ 确定性有限自动机 , 接受 w 字符串 \} ADFA​={: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​ ;

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

证明上述计算问题是可判定的 ,

需要 构造一个图灵机 , 认识该语言 , 并且该图灵机一定是判定机 , 即可证明计算问题是可判定的 ;

构造图灵机 M \rm M M , 输入 < B , w > \rm 字符串 , 即输入确定性有限自动机 B \rm B B 所能接受的字符串 w \rm w w ,

引入 丘奇-图灵命题 ,

没有必要设计图灵机 , 这里只需要设计算法即可 , 根据 丘奇-图灵命题 , 任何算法都对应一个图灵机 ,

这样就避免了设计一个图灵机 , 这个很复杂的过程 ;

证明过程 :

① 模仿 : 给定输入字符串 w \rm w w 之后 , 模仿 确定性有限自动机 B \rm B B 在 w \rm w w 字符串上进行计算 ;

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

确定性有限自动机 B \rm B B 在任何输入字符串 w \rm w w 上计算 , 一定会停机 , 即 在 字符串 w \rm w w 读取完毕的那一时刻 , 自动机就会停机 , 此时一定会出现一个 接受状态 或 拒绝状态 ;

上述自动机会停机 , 图灵机 M \rm M M 模仿该自动机进行计算 , 也会相应的进行停机 , 肯定能得到一个 接受 / 拒绝 的结果 , 因此 图灵机 M \rm M M 肯定是一个判定机 ;

因此 确定性有限自动机的接受问题 , 是可判定的 ;

问题不重要 , 重要的是理解证明问题的思路 , 过程 ;