问题 - 序言中的形式语言

Question

我正在尝试构建一个 DCG，它可以识别与此形式匹配的所有列表：a^nb^2m c^2m d^n。
我写下了以下规则：
<代码>s --> [].
<代码>s -->广告。
广告 --> a、ad、d。
广告 -->公元前。
<代码>BC --> b、b、bc、c、c。
<代码>BC --> [].
一个 --> [一]。
<代码>b --> [b].
<代码>c --> [c].
<代码>d --> [d].

当我尝试使用这些规范评估字符串时，例如列表[a,b,b,c,c,d]，它可以工作。但是，当我尝试评估查询短语（s，X）以便我可以看到此语法返回的所有可能的字符串时，它会无限循环。

我构建 DCG 的方式有问题吗？

Answer 1

您可以通过迭代加深来公平地枚举字符串：

?- length(Ls, _), phrase(s, Ls).
Ls = [] ;
Ls = [] ;
Ls = [a, d] ;
Ls = [a, a, d, d] ;
Ls = [b, b, c, c] ;
etc.

Answer 2

@Simon 使用 DGC 的方法是正确的，但您的尝试存在两个问题。

第一个是您在如下子句中保留了递归：

ad --> a, ad, d.

这就是它循环到无穷大的原因之一。

第二个问题是这种形式语言无法构建为上下文无关语法，因此您需要一个额外的变量，例如 count。

s(Count) --> a(Count),b(Count),c(Count),d(Count).
a(0) --> [].
a(succ(Count)) --> [a],a(Count).
b(0) --> [].
b(succ(Count)) --> [b,b],b(Count).
c(0) --> [].
c(succ(Count)) --> [c,c],c(Count).
d(0) --> [].
d(succ(Count)) --> [d],d(Count).

然后使用以下目标 s(_, L, []) 进行查询。

我知道这是一个老问题，但也许从现在开始有人会发现正确的答案很有用。

Answer 3

我没有看到这个问题的序言部分。答案很大程度上取决于你如何实现这个语法。

我最好的猜测是颠倒规则的顺序，首先应用终止规则。

Answer 4

我写这篇文章是为了帮助限制解决方案，即使有无限的解决方案。但我意识到有一种方法可以重新排列规则以首先获得更短的结果。

因为 ad --> a, ad, d. 在 ad -->; 之前评估bc. 它试图满足 ad --> a, ad, a. 在 ad --> 之前公元前。。我会放 ad --> bc. 位于 ad 之前 -->一个，广告，一个。。 bc 也是如此 --> b、b、bc、c、c。 和 bc --> []. 规则

正如 arian 指出的那样，首先应用终止规则，将确保首先找到较短的解决方案。

我还想指出的是 [] s 和 s -> 有两种解决方案广告-> BC-> [] 我会消除 s --> []. 因为它是多余的。

总而言之，我会尝试这个解决方案：

s --> ad.
a --> [a].
b --> [b].
c --> [c].
d --> [d].
ad --> bc.
bc --> [].
ad --> a, ad, d.
bc --> b, b, bc, c, c.

原始帖子：

我必须查找如何进行计数（自从我做序言以来已经有一段时间了）但是数量是无限的，并且由于序言试图找到所有解决方案，它永远不会停止寻找，尽管我确信在此之前您会遇到堆栈溢出或一些错误:)。

限制结果数量的一种方法是限制解的大小

 phrase(s, X), length(X, 4).

获取恰好具有 4 个值的所有解，将其

X = [a, a, d, d]
X = [b, b, c, c]

增加到 6 将产生：

X = [a, a, a, d, d, d]
X = [a, b, b, c, c, d]

或使用范围：

 phrase(s, X), length(X, Y), Y >= 4 , Y < 10, Y != 6.