语言可判定性

如果有一个图灵机接受并停止每个输入字符串w，则一种语言称为可判定或递归。每种可判定语言都是图灵可接受的。

可判定性和可判定语言

如果P的所有“是”实例的语言L是可判定的，则决策问题 P是可判定的。

对于可判定语言，对于每个输入字符串，TM 在接受或拒绝状态下停止，如下图所示 -

可判定语言

实施例1

找出以下问题是否可判定 -

数字“m”是质数吗？

解决方案

质数 = {2, 3, 5, 7, 11, 13, …………..}

将数字“m”除以“2”和“√m”之间从“2”开始的所有数字。

如果这些数字中的任何一个产生余数零，则进入“拒绝状态”，否则进入“接受状态”。所以，这里的答案可以是“是”或“否”。

因此，这是一个可判定的问题。

实施例2

给定一个正则语言L和字符串w，我们如何检查w ∈ L？

解决方案

取接受L的 DFA并检查w是否被接受

DFA 1

一些更可判定的问题是 -

  • DFA 接受空语言吗？
  • 对于正则集， L 1 ∩ L 2 = ∅ 吗？

注意-

  • 如果语言L是可判定的，那么它的补语L'也是可判定的

  • 如果一种语言是可判定的，那么它就有一个枚举器。