1

如果我有一个上下文无关语法 G 使得 G 的语言为零，那么 G 是可判定的吗？

我知道答案是肯定的，但我无法证明这一点。我的第一个想法是说只有一个状态 q1，它是相当于 G 的图灵机的启动状态和接受状态。这台机器将不接受任何输入并立即停止并接受，因为它已达到接受状态状态。这是一个可以接受的答案，还是我离开这里？

编辑：

正如乔尔在下面所说，我描述的语言接受所有字符串。为了解决这个问题，我建议使用第二台机器 G'。G' 有 3 个状态，开始状态 q1、接受状态 q2 和拒绝状态 q3。q1 在 G' 字母表中的所有符号上都转换为 q3，q2 也是如此。q1 有一个到 q2 的 epsilon 转换。因此，如果提供给 G' 的字符串中存在任何符号，则 G' 将拒绝。如果没有符号，唯一的选择是将 epsilon 转换为接受状态。听起来怎么样？

编辑：

上面的解决方案被证明可以接受语言 L(G') = {""}。

4

1 回答 1

1

正如你所说，答案是肯定的。一个普遍的证明是这样一个事实，即给定一个 CFG G，您可以轻松（很好地）构造一个 TM 使用该语法模拟推导。但是，您正在寻找空语言的简短证明。（在这种情况下，您拥有 CFG 的事实是无关紧要的。）

您走在正确的轨道上，因为如果您可以构建一个对于给定语言 L 总是停止的 TM，那么 L 是可判定的。但是，您描述的机器实际上将接受每个字符串，即由字母表上每个可能的字符串组成的语言。那是因为如果启动状态也是一个接受状态，那么图灵机一启动就会立即接受。它不必读取整个输入字符串（或其任何部分）即可接受。

要定义不接受任何内容的 TM，请让接受状态集为空。为了保证你的机器总是停止，你的转换函数也可以是空的。

于 2011-03-22T06:05:59.233 回答