语言可判定性



如果存在一台图灵机,对于每一个输入字符串 w 都能接受并停机,则称该语言为可判定递归语言。每个可判定语言都是图灵可接受的。

Decidability and Decidable Languages

如果所有肯定例子的语言 L 是可判定的,则判定问题 P 是可判定的。

对于可判定语言,对于每个输入字符串,图灵机都会在接受状态或拒绝状态停机,如下图所示:

Decidable Language

示例 1

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

数字‘m’是否为素数?

解答

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

从 ‘2’ 开始,将数字 ‘m’ 除以 ‘2’ 到 ‘√m’ 之间的全部数字。

如果任何这些数字产生余数为零,则进入“拒绝状态”,否则进入“接受状态”。因此,答案可以是“是”或“否”。

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

示例 2

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

解答

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

DFA 1

一些其他的可判定问题:

  • DFA 是否接受空语言?
  • 对于正则集,L1 ∩ L2 = ∅ 是否成立?

注意

  • 如果语言 L 是可判定的,则其补集 L' 也是可判定的。

  • 如果一个语言是可判定的,那么它就存在枚举器。

广告