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

文章目录

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

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

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

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

是字符串 ;

是确定性有限自动机 ;

接受

;

将

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

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

的语言

;

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

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

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

构造图灵机

, 输入

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

所能接受的字符串

,

引入 丘奇-图灵命题 ,

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

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

证明过程 :

① 模仿 : 给定输入字符串

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

在

字符串上进行计算 ;

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

接受 , 否则就让 图灵机

拒绝 ;

确定性有限自动机

在任何输入字符串

上计算 , 一定会停机 , 即 在 字符串

读取完毕的那一时刻 , 自动机就会停机 , 此时一定会出现一个 接受状态 或 拒绝状态 ;

上述自动机会停机 , 图灵机

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

肯定是一个判定机 ;

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

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