Подсчет определенных грамматических рекурсий в прологе

Question

У меня есть следующая грамматика Пролога:

s-->[a],s,[b].
s-->[].

Это приведет к тому, что такие слова, как [a, a, b, b], будут приняты в противоположность словам, подобным [a, b, a, b]. Короче говоря, грамматика - это, очевидно, a ^ n b ^ n. Теперь я хочу вернуть пользователю. Как я могу рассчитать n?

Answer 1

s(X)-->[a],s(Y),[b],{X is Y+1}.
s(0)-->[].

Необходимо указать параметры для нетерминалов DCG. Пожалуйста, позаботьтесь о том, чтобы равенство не работало точно так же, как назначение императивных языков программирования, поэтому X означает Y + 1.

Некоторые примеры выходных данных:

s(X,[a,b,b,b],[]).
false.

s(X,[a,a,a,b,b,b],[]).
X = 3 ;
false.

Answer 2

Ответы от @ thequark и от @ LittleBobbyTables отлично работают при использовании с заземленными строками.

Но что, если они не ограничены по длине, как в следующих запросах?

?- phrase(s(3),_).               % expected: success   
%                                  observed: no answer(s)

?- phrase(s(-10),_).             % expected: failure
%                                  observed: no answer(s)

Мы, конечно, хотим, чтобы запросы, подобные приведенному выше, заканчивались повсеместно! Давайте используем clpfd и напишем:

:- use_module(library(clpfd)).

s(0) --> [].
s(N) --> {N#>0,N#=N0+1},[a],s(N0),[b].

Примеры запросов:

?- phrase(s(N),[a,a,a,a,b,b,b,b]).
N = 4 ;                          % works like in the other answers
false.

?- phrase(s(3),Xs).
Xs = [a,a,a,b,b,b] ;             % now, this works too!
false.                           % (terminates universally)

?- phrase(s(-10),_).             % fails, like it should
false.

Answer 3

s(N, M) --> [a], {N1 is N + 1}, s(N1, M), [b].
s(N, N) --> [].
s(N) --> s(0, N).

Использование:

?- phrase(s(N), [a,a,a,b,b,b]).
N = 3