我在一个本科班，我们现在正在学习形式语法。我问我的老师是否有任何已知的规则来创建上下文无关语法
1) 保证产生明确的语法。2) 允许创建任何可能的明确语法。
我很清楚，确定语法是否模棱两可是不可判定的。我不确定上述想法是否可以简化为，但是在摆弄了一下之后，我想不出一种方法来进行这种简化。也就是说，我真的不是简化或语法方面的专家。我尝试了一段时间的谷歌搜索，但我只找到了关于不确定性的页面。有人知道吗？
问问题
126 次
1 回答
0
我想你知道的足够多，可以自己解决这个问题，得出一个令人满意的结论。
考虑一组我声称将满足您的约束的规则：它们将只接受明确的语法，并且他们将接受所有明确的语法。也就是说，当且仅当语法 G 遵循规则时，它才是明确的。
现在，为了有用，我的规则集必须能够通过查看语法来判断它是否遵守规则。也就是说，对于任何语法 G，都必须有一个有效的程序来确定命题“G 遵循规则”的真值。
您现在也许可以看到它的发展方向。如果您不这样做，请给自己一分钟；它可能会来找你。
假设我有这样一套规则。如果我的描述是正确的，我们现在有一个有效的程序来确定语法是否遵循规则。我们知道，如果文法遵循规则，那么文法是明确的。我的规则现在听起来很像声称有一个有效的程序来确定语法是否明确。你提到的可判定性结果表明没有这样有效的程序。
因此，您无需检查即可知道，我的规则集并不满足所有三个约束条件。要么我的规则确实允许一些模棱两可的语法（违反你的第一个约束），要么我的规则拒绝一些明确的语法（违反你的第二个约束），或者没有有效的程序来确定一个语法是否符合我的规则（违反我们的直觉理解“一套规则”）。
[附录]
如果我们放宽对规则集的约束，让规则即使并不总是终止也可以算作有用，那么我认为答案可能是“是”，这是基于任何程序都可以制定定理的一般原则当且仅当程序终止时为真，并且对于任何定理，人们都可以构造一个程序，该程序将在当且仅当该定理为真时终止。（这有一个名字，但我现在正在空白。）
Goedel 的完备性定理建立了一种算法，该算法将生成（给定足够的时间）逻辑系统的任何定理；问题是它不能保证终止，因此在任何给定的时间段之后，我们可能无法判断我们是否正在处理最终将被识别的真实陈述，或者算法可能不会终止的虚假陈述。
也就是说，我不知道所讨论的规则除了以逻辑形式对语法中的歧义定义（或不存在）进行陈述之外，还有其他任何东西。构建这种设备的最简单方法是生成所有可能的文法，按长度升序排列，并为每个文法进行证明，一次一步，每个文法与其他文法轮流进行。（如果我们在一个语法上工作直到我们得到一个结果，我们可能永远不会到达下一个语法，所以我们必须执行一种循环，很像通过生成所有派生来从一个语法中生成所有句子的简单算法.)
我希望这有帮助。
于 2015-02-13T03:11:29.260 回答