从模糊语法转换为明确语法

Question

我有一个含糊不清的无上下文文法，其中包括以下内容：

s --> [0],s,[1].
s --> [0],s.
s --> [].

当然，对于00011，我可以绘制出两个不同的解析树，这显然是有歧义的。因此，我需要编写一个无歧义的语法来描述相同的语言。我的想法是：

   s --> [0],s,[1].
   s --> [0],a.
   s --> [].
   a --> [0],a.
   a --> [].

这个好吗？我怎么证明呢？

- Vous

---

0和1是我们的字母表。[]表示空集合，而“，”在Prolog中使用。当在Prolog上时，我们会将S -> 0S1写成s --> [0], s, [1]。 - Vous

虽然没有算法解决方案来验证语法是否模糊或等效，所以你唯一的技巧是能力和分析证明。 - Grijesh Chauhan

你必须证明在你的第二个语法中，对于语言中的每个字符串只有一棵派生树。如果我教你如何处理这类问题，答案会变得非常冗长（你可以等一下吗？）。你理解运算符优先级或生成流程吗？ - Grijesh Chauhan

为了证明你的答案，请告诉你的老师：“在我第二个版本的语法中，您必须首先生成所有的1，然后一旦您转到s--> [0]，a. 产生式，就不能再添加1。 （如果您认为0和1都是运算符，则0的优先级高于1，因为它在解析树中的位置较低）”。 您可以阅读此答案以了解优先级概念：https://dev59.com/KHPYa4cB1Zd3GeqPim-R#17170820 - Grijesh Chauhan

现在我明白了。非常感谢你。 - Vous

Answer 1

那么如何证明模糊性呢？在Prolog中，对于具体的句子，这是很容易实现的：

?- length(Xs,N), bagof(t,phrase(s,Xs),[_,_|_]).   
   Xs = [0,0,1], N = 3
;  Xs = [0,0,0,1], N = 4
;  Xs = [0,0,0,0,1], N = 5
;  Xs = [0,0,0,1,1], N = 5
;  Xs = [0,0,0,0,0,1], N = 6
;  Xs = [0,0,0,0,1,1], N = 6
;  Xs = [0,0,0,0,0,0,1], N = 7
;  ... .

这证明了具体长度存在歧义，并提供了相关的反例。

然而，有一个警告可能只在一段时间后才能显示出来：bagof/3 必须以某种方式存储整个解集。因此，如果这个集合非常大，bagof/3 可能会溢出。以下查询避免了这个错误，但代价是得到了冗余的解：

?- length(Xs,N), phrase(s,Xs), bagof(t,phrase(s,Xs),[_,_|_]).
   Xs = [0,0,1], N = 3
;  Xs = [0,0,1], N = 3
;  Xs = [0,0,0,1], N = 4
;  Xs = [0,0,0,1], N = 4
;  Xs = [0,0,0,1], N = 4
;  Xs = [0,0,0,1,1], N = 5
;  Xs = [0,0,0,1,1], N = 5
;  Xs = [0,0,0,0,1], N = 5
;  Xs = [0,0,0,1,1], N = 5
;  Xs = [0,0,0,0,1], N = 5
;  Xs = [0,0,0,0,1], N = 5
;  Xs = [0,0,0,0,1], N = 5
;  Xs = [0,0,0,0,1,1], N = 6
;  ... .

通过您改进的语法，查询循环。这意味着系统无法找到反例。至少不是长度低于1000的反例，这是我测试的内容。

关于在Prolog中编写DCGs的一些常规注释：

• 尝试将递归情况放在最后，这可能会节省一些空间。

• 您可能希望使用双引号字符串来表示终端。有关更多信息，请参见此答案。

- false