prolog - 我正在尝试使用 DCG 创建一种语言 a^nb^n-1 c^n-2 但无法使 succ(0) 处理 n

Question

s(Count) --> a(Count), b(Count), c(Count).

a(0) --> [].
a(succ(Count)) --> [a], a(Count).

b(0) --> [].
b(succ(succ(Count))) --> [b], b(Count).

c(0) --> [].
c(succ(succ(succ(Count)))) --> [c], c(Count).

好吧，很容易为每个规则使用 succ(0) 创建像 a^nb^nc^n 这样的语言，但是当涉及到改变 ab 和 c 的每个块的 n 时，它不起作用。

Answer 1

查看您的条款，例如：

c(0) --> [].
c(succ(succ(succ(Count)))) --> [c], c(Count).

请注意，您只匹配两种情况——零个或三个字符，但是一两个呢？修改c以考虑每个可接受的长度似乎是一个死胡同，但更容易指定相对于您的s 数量和s 在您控制它们的地方c想要多少 s ，即：abs

s(succ(succ(Count))) --> a(succ(succ(Count))), b(succ(Count)), c(Count).

这自然会转化为您的规范：对于N至少两个，接受N as、N-1 bs 和N-2 cs。

现在其余的很容易就位：

a(0) --> [].
a(succ(Count)) --> [a], a(Count).

b(0) --> [].
b(succ(Count)) --> [b], b(Count).

c(0) --> [].
c(succ(Count)) --> [c], c(Count).

当然，您可以用通用子句替换它们char(Char, Count)（作为练习留下）。

?- phrase(s(succ(succ(succ(0)))), X).
X = [a, a, a, b, b, c].

Answer 2

除了@firefrorefiddle 的回答，我还想注意三件事。首先，在使用皮亚诺数时，更习惯使用函子 s/1 来表示后继，使用 X 等单个字母表示变量，从而获得更小的项：

s(X)            succ(Count)
s(s(X))         succ(succ(Count))
s(s(s(X)))      succ(succ(succ(Count)))
s(s(s(s(X))))   succ(succ(succ(succ(Count))))
.               .
.               .
.               .

其次，为了进一步提高可读性，最好为 DCG 选择一个不同的名称，比如 language//1 而不是 s//1。第三，您可以定义一个更通用的 DCG，让您指定一个元素及其在列表中的出现次数a，b而不是为 和 编写相同的 DCG 规则。c将所有这些放在一起，您的 DCG 可能看起来像这样：

language(s(s(X))) -->
   element_frequency(a,s(s(X))),
   element_frequency(b,s(X)),
   element_frequency(c,X).

element_frequency(_E,0) -->
   [].
element_frequency(E,s(X)) -->
   [E],
   element_frequency(E,X).

在上面的代码中，lan​​guage//1 对应于代码中的 s//1，element_frequency//2 是 a//1、b//1 和 c//1 的替换。如果您查询此 DCG，您会发现它仍然会产生与 @firefrorefiddle 帖子中的答案相同的答案，例如：

   ?- phrase(language(s(s(s(0)))),L).
L = [a,a,a,b,b,c]

Answer 3

DCG 的 [] 随时匹配。让我们颠倒 a,b,c 规则。

s(Count) --> a(Count), b(Count), c(Count).

a(succ(Count)) --> [a], a(Count).
a(0) --> [].

b(succ(succ(Count))) --> [b], b(Count).
b(0) --> [].

c(succ(succ(succ(Count)))) --> [c], c(Count).
c(0) --> [].

:- s(N,[a,a,a,a,a,a,b,b,b,c,c],[]),writeln(N).
:- halt.