Frage - formale Sprache in Prolog

Question

Ich versuche, eine DCG zu erstellen, die alle Listen erkennt, die dieser Form entsprechen: a^n b^2m c^2m d^n.
Ich habe die folgenden Regeln geschrieben:
s --> [].
s --> ad.
ad --> a, ad, d.
ad --> bc.
bc --> b, b, bc, c, c.
bc --> [].
a --> [a].
b --> [b].
c --> [c].
d --> [d].

Wenn ich versuche, eine Zeichenfolge mit diesen Spezifikationen zu bewerten, wie die Liste [a,b,b,c,c,d], funktioniert es. Aber wenn ich versuche, die Abfrage phrase(s, X) zu bewerten, so dass ich alle möglichen Zeichenfolgen sehen kann, die von dieser Grammatik zurückgegeben werden, läuft es in Unendlichkeit.

Ist etwas falsch mit der Art, wie ich das DCG gebaut habe?

Answer 1

Sie können die Saiten ziemlich mit iterativer Vertiefung aufzählen:

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

Answer 2

Ich sehe den Prolog Teil dieser Frage nicht. Die Antwort hängt stark davon ab, wie Sie diese Grammatik implementiert haben.

Meine beste Schätzung wäre, die Reihenfolge der Regeln umzukehren, um die Abschlussregeln zuerst anwenden zu lassen.

Answer 3

Ich schrieb dies als eine Möglichkeit Grenze Lösungen zu helfen, auch wenn es unendlich viele Lösungen. Aber ich erkannte, dass es eine Möglichkeit geben würde, die Regeln neu zu ordnen, um zuerst kürzere Ergebnisse zu erhalten.

Da ad --> a, ad, d. vor ad --> bc. ausgewertet wird versucht es ad --> a, ad, a. vor ad --> bc. gerecht zu werden. Ich würde ad --> bc. vor ad --> a, ad, a. setzen. Das gleiche gilt für die bc --> b, b, bc, c, c. und bc --> []. Regeln

Wie Arian wies darauf hin, die Abschlussregeln zuerst angewendet haben, würde sicherstellen, dass die kürzeren Lösungen zuerst gefunden werden.

Ich möchte auch darauf hinweisen, dass es zwei Lösungen für [] s und s -> ad -> bc -> [] Ich würde s --> []. zu beseitigen, wie es redundant ist.

Alles in allem würde ich diese Lösung versuchen:

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

ORIGINAL POST:

Ich hatte bis zu schauen, wie das Zählen zu tun (es ist eine Weile her, seit ich Prolog tat) Aber es gibt eine unendliche Zahl und seit Prolog versucht, alle Lösungen zu finden, hört es nie auf zu suchen, obwohl ich sicher bin, dass du einen Stack über den Flow triffst oder einen Fehler davor hast :).

Eine Möglichkeit, die Anzahl der Ergebnisse zu begrenzen, ist die Größe der Lösung

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

Ruft alle Lösungen mit genau 4 Werte zu begrenzen, die

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

zuzunehmen 6 wäre ergäbe :

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

oder benutzen Bereiche: