computer-science - 正则、图灵可判定和图灵可识别是什么意思？

Question

我知道这个问题之前已经被问过，但老实说我不太明白。

我目前正在研究计算理论，我正在研究“证明一种语言是可判定的、可识别的或规则的”这一术语。

用最简单的术语来说，它们的实际含义是什么？我们如何证明这些事情？

Answer 1

我们正在谈论一种语言 字母表 ，这意味着 ( 由来自 的字母组成的单词组成。

<强> 可判定
意味着存在一台图灵机 ，这样 对于任何输入词都会停止并接受 对于任何输入单词，停止并拒绝 .

<强> 易于识别
意味着存在一台图灵机 ，这样 对于任何输入词都会停止并接受 对于任何输入停止或不停止(但不是停止并接受!) .

另请参阅Recognizable vs Decidable on MathExchange为了区别。

<强> 有规律
意味着 可以通过正则表达式创建。值得注意的是，理论计算机科学中的这些正则表达式与 PERL 或 Java 等编程语言中已知的正则表达式功能不同。事实上，这些正则表达式确实比正则表达式更强大(不知道这是否是正确的英文术语)。

给出了正则表达式的良好定义here :

对于字母表

• 和 (空集和空词)是正则表达式
• 对于任何 (字母表中的任何字母)是正则表达式
• 如果 和 是正则表达式，这些也是正则表达式:
  • (意思是或)
  • (意味着 和 的串联)
  • (意思是 、任意次数的 重复或空词 )

除此之外没有什么是正则表达式。

我们如何证明这样的事情？

图灵机

为了证明可判定性或可识别性，通常最简单的方法是为图灵机提供所需的属性。因为Church-Turing thesis ，任何编程语言都像图灵机一样强大。因此，在我的类(class)中，用编程语言或伪代码提供算法是完全可以接受的。

请注意，任何可识别的语言也是可判定的(但反之则不然)。

正则表达式

为了证明正则性，大多数时候最简单的方法是提供构建语言的正则表达式。有时需要证明正则表达式确实准确地构造 ，这通常不太困难(通常很明显)。

在许多讲座中，有一个关于正则表达式的约定，它允许更直观和更短(但不是更强大)的语法。

有趣的是，常规语言正是 finite automatons 可以识别的语言。 。请注意，任何常规语言也是可判定的(因此是可识别的)。

为了反驳规律性，我只想提及 pumping lemma for regular languages .