Вопрос - формальный язык в прологе

Question

Я пытаюсь создать DCG, которая распознает все списки, соответствующие этой форме: a^n b^2m c^2m d^n.
Я написал следующие правила:
s --> [].
s --> ad.
ad --> a, ad, d.
ad --> bc.
bc --> b, b, bc, c, c.
bc --> [].
a --> [a].
b --> [b].
c --> [c].
d --> [d].

Когда я пытаюсь оценить строку с этими спецификациями, например, список [a,b,b,c,c,d], это работает. Но когда я пытаюсь оценить запрос phrase(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

@ Саймон, подход к использованию 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

Я написал это как способ помочь ограничить решения, даже если есть бесконечные решения.Но я понял, что будет способ изменить правила, чтобы сначала получить более короткие результаты.

Поскольку ad --> a, ad, d. оценивается до ad --> bc., он пытается удовлетворить ad --> a, ad, a. до ad --> bc..Я бы поставил ad --> bc. перед ad --> a, ad, a..То же самое относится к bc --> b, b, bc, c, c. и bc --> []. правилам

Как указал Ариан, сначала применяются правила завершения, гарантировавшее, что более короткие решения будут найдены первыми.

Я также хочу указатьиз того, что есть два решения для [] s и s -> ad -> 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.

Answer 4

Я не вижу пролог в этом вопросе. Ответ сильно зависит от того, как вы реализовали эту грамматику.

Моим лучшим предположением было бы изменить порядок правил, чтобы сначала применялись правила завершения.