CFG是否使用可判断的nil语言？

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

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

编辑：

乔尔下面说的，我描述的语言接受所有字符串。为了解决这个问题，我提出了第二台机器G'。 G'具有3个状态，起始状态q1，接受状态q2和拒绝状态q3。 q1在G'的字母表中的所有符号上过渡到q3，q2也是如此。 q1有一个ε过渡到q2。因此，如果在馈送给G'的字符串中存在任何符号，则G'将被拒绝。如果没有符号，唯一的选择是将epsilon转换到accept状态。听上去怎么样？

编辑：

将上述溶液被证明接受语言L（G'）= { “”}。

来源

2011-03-22 Darkhydro

我想我们可能会使用不同的术语。 “G的语言是零”是指L（G）= {}，即空集？或者，你的意思是L（G）= {“”}，即由恰好一个字符串组成的语言，即空字符串？人们通常认为，不存在接受状态的转变，所以当你达到接受状态时，你会停下来。有了这个假设，你的原始TM接受了一切。您在Edit中描述的TM接受L = {“”}，我认为这是您的意图。我在答复中描述的TM没有任何结果。也就是说，它接受L = {}。 – 2011-03-22 07:08:07

@Joel我的意思是L（G）= {nil}，我相信这相当于你的陈述L（G）= {}。如果从未达到接受状态（因为没有？），可以多解释一下答案如何接受该语言（因为没有？） – Darkhydro 2011-03-22 17:18:12

根据定义，如果机器_M_在给定输入_s_时达到接受状态，则接受字符串_s_。同样根据定义，_L（M）_，被称为“M接受的语言”，是_M_接受的所有字符串的集合。 _L（M）_是一组**字符串。但实际上，这一套可能是空的。如果机器没有接受状态，那么它不可能接受任何给予它的字符串。因此_L（M）_是空集。您的G'机器只接受一个字符串，即零长度字符串。因此，_L（G'）_ = {“”}。 – 2011-03-22 22:53:04

正如你所说，答案是肯定的。一般的证明是，给定一个CFG G你可以很容易（很好地）构造一个TM来模拟使用该语法的派生。但是，您正在寻找空白语言的简短证明。（事实上，在这种情况下你有一个CFG是无关紧要的。）

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

要定义不接受任何内容的TM，让接受状态集为空。为确保您的机器始终处于停止状态，您的转换功能也可以为空。

来源

2011-03-22 06:05:59

我不确定我是否理解。我的印象是，机器不仅要停下来，还要接受。机器可以暂停然后拒绝语言，因为（我认为）在您的示例中就是这种情况。 – Darkhydro 2011-03-22 06:25:01

关于术语/概念的注意事项。我们讨论接受或拒绝给定字符串的机器。由此我们定义了“M接受的语言”的概念，并且我们说“机器M接受语言L”。但是，我们并不是说“机器M拒绝语言L”。相反，你会说“M接受的语言不等于L”。 – 2011-03-22 23:41:30

CFG是否使用可判断的nil语言？

回答

相关问题