什么是递归语言和递归可枚举语言？

在学习计算理论 (TOC) 中的递归可枚举语言之前，让我们先了解递归语言的概念。

递归语言

如果语言 L 是某个图灵机 (TM) 接受的字符串集合，并且该图灵机在所有输入上都会停止运行，则语言 L 是递归的（可判定的）。

示例

当图灵机到达最终状态时，它会停止运行。我们也可以说，当图灵机 M 达到状态 q 以及要扫描的当前符号“a”，并且 δ(q, a) 未定义时，M 会停止运行。

有些图灵机在某些输入上永远不会停止运行，因此我们需要区分由在所有输入字符串上都停止运行的图灵机接受的语言和由在某些输入字符串上永远不会停止运行的图灵机接受的语言。

递归可枚举语言

如果语言 L 是某个 TM 接受的字符串集合，则语言 L 是递归可枚举的。

如果 L 是递归可枚举语言，则：

如果 w ∈ L，则 TM 会在最终状态停止运行；

如果 w ∉ L，则 TM 会在非最终状态停止运行或永远循环。

如果 L 是递归语言，则：

如果 w ∈ L，则 TM 会在最终状态停止运行；

如果 w ∉ L，则 TM 会在非最终状态停止运行。

递归语言也是递归可枚举的

证明 - 如果 L 是递归的，则存在一个 TM 可以判定语言中的成员，则：

  • 如果 x 属于语言 L，则 M 接受 x。

  • 如果 x 不属于语言 L，则 M 拒绝 x。

根据定义，M 可以识别那些被接受的字符串。

更新于：2021年6月16日

27K+ 次浏览

启动您的 职业生涯

完成课程获得认证

开始学习
广告