1

G 是给定的 CFG，L(G) 是规则的吗？这是一个无法确定的问题。

但我的论点是，语言是给定的，如果我可以做以下任何事情，那么它将是常规的，否则将是非常规的：

  • 创建 DFA/NFA
  • 编写左线性或右线性语法
  • 编写正则表达式

请告诉我为什么它无法确定？

4

1 回答 1

2

“不可判定”意味着没有算法可以决定问题。让我们深入研究这些术语的含义。

算法是您可以编码到图灵机中的任何东西。图灵机没有创造力，他们不思考，他们不能幸运或学习新事物来尝试。它们以一种方式编码，然后必须在所有输入上都以相同的方式工作，而没有任何改变的可能性。改变它的行为，你就有了一台新的图灵机。

在这种情况下决定意味着正确地确定每个问题实例的答案是肯定的还是否定的。您必须能够在有限的时间内以 100% 的把握对每个实例说是或否；大多数时候只能说“是”或“不”，甚至两者都说是不够的。

那么回答你的问题：

  • 你（大概）不是图灵机
  • 没有什么能阻止您（或图灵机）回答大量感兴趣的实际问题实例的问题
  • 目前尚不清楚这个问题是否对人类来说是不可判定的；我们只能证明它对于图灵机（和等效的计算系统）是不可判定的。
  • Church-Turing论文推测人类的计算能力并不超过图灵机，但这并没有得到证实
于 2015-09-15T17:43:34.633 回答