语言可判定性

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

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

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

示例 1

确定以下问题是否可判定 −

数字'm'是质数吗？

解决方案

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

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

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

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

示例 2

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

解决方案

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

一些更可判定的问题是 −

• DFA 是否接受空语言？
• L₁ 是否 ∩对于正则集，L₂ = ∅？

注意 −

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

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