Я пытаюсь создать язык a^n b^n-1 c^n-2, используя DCG, но не могу сделать 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).

Что ж, легко создать такой язык, как ^n b^n c^n, используя succ(0) для каждого правила, но когда дело доходит до изменения n для каждого блока a b и c, он не работает.

Answer 1

Глядя на ваши статьи, как:

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

Обратите внимание, что вы сопоставляете только два случая - ноль или три символа, но как насчет одного или двух? Изменение c для учета любой приемлемой длины кажется тупиком, гораздо проще указать, сколько cвы хотите по отношению к вашему числу aс и bв том месте, где вы контролируете их все, то есть в s:

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

Это естественно переводит к вашей спецификации: для N по крайней мере двух, принять Nas, N-1bс и N-2cs.

Теперь все остальное легко встает на свои места:

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 а также cВы можете определить более общую DCG, которая позволяет вам указать элемент и номер его вхождения в списке. Собрав все это вместе, ваш 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).

В приведенном выше коде язык // 1 соответствует s // 1 в вашем коде, а element_frequency//2 является заменой для //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.