Automata Theory 简明教程

Language Decidability

如果存在一台图灵机，接受并停止处理每个输入字符串 w ，则称为 Decidable 或 Recursive 语言。每个可判定的语言都是图灵可接受的。

A language is called Decidable or Recursive if there is a Turing machine which accepts and halts on every input string w. Every decidable language is Turing-Acceptable.

decidability and decidable languages

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

A decision problem P is decidable if the language L of all yes instances to P is decidable.

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

For a decidable language, for each input string, the TM halts either at the accept or the reject state as depicted in the following diagram −

decidable language

Example 1

找出以下问题是否可判定的 −

Find out whether the following problem is decidable or not −

数字“m”是否为素数？

Is a number ‘m’ prime?

Solution

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

Prime numbers = {2, 3, 5, 7, 11, 13, …………..}

将数字 ‘m’ 除以从“2”到“√m”之间的所有数字，从“2”开始。

Divide the number ‘m’ by all the numbers between ‘2’ and ‘√m’ starting from ‘2’.

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

If any of these numbers produce a remainder zero, then it goes to the “Rejected state”, otherwise it goes to the “Accepted state”. So, here the answer could be made by ‘Yes’ or ‘No’.

Hence, it is a decidable problem.

Hence, it is a decidable problem.

Example 2

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

Given a regular language L and string w, how can we check if w ∈ L?

Solution

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

Take the DFA that accepts L and check if w is accepted

dfa1

另一些可判定的问题为 −

Some more decidable problems are −

  1. Does DFA accept the empty language?

  2. Is L1 ∩ L2 = ∅ for regular sets?

Note −

Note −

  1. If a language L is decidable, then its complement L' is also decidable

  2. If a language is decidable, then there is an enumerator for it.