Pregunta - lenguaje formal en prolog

Question

Estoy intentando crear un DCG que reconozca todas las listas que coinciden con este formulario: a^n b^2m c^2m d^n.
me han redactado las siguientes reglas:
s --> [].
s --> ad.
ad --> a, ad, d.
ad --> bc.
bc --> b, b, bc, c, c.
bc --> [].
a --> [a].
b --> [b].
c --> [c].
d --> [d].

Cuando intento evaluar una cadena con esas especificaciones, como la lista [a,b,b,c,c,d], funciona. Pero cuando trato de evaluar la consulta phrase(s, X) para que pueda ver todas las cadenas posibles devueltas por esta gramática, se convierte en infinito.

¿Hay algún problema con la forma en que he construido el DCG?

Answer 1

Puede enumerar las cuerdas de manera justa con profundización iterativa:

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

Answer 2

No veo el prólogo como parte de esta pregunta. La respuesta depende en gran medida de cómo implemente esta gramática.

Mi mejor opción sería invertir el orden de las reglas, tener las reglas de terminación aplicadas primero.

Answer 3

escribí esto como una manera de ayudar a las soluciones de carrera a pesar de que existen infinitas soluciones. Pero me di cuenta de que habría una forma de reorganizar las reglas para obtener resultados más cortos primero.

Debido ad --> a, ad, d. se evalúa antes ad --> bc. se trata de satisfacer ad --> a, ad, a. antes ad --> bc.. Yo pondría ad --> bc. antes de ad --> a, ad, a.. Lo mismo ocurre con las reglas bc --> b, b, bc, c, c. y bc --> [].

Como arian señaló que las reglas de terminación se aplicaron primero, se aseguraría de que las soluciones más cortas se encuentren primero.

También quiero señalar que hay dos soluciones para [] sys -> ad -> bc -> [] Yo eliminaría s --> []. ya que es redundante.

en general me gustaría probar esta solución:

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

post original:

tuve que buscar la manera de hacer el recuento (que ha pasado un tiempo desde que hice prólogo), pero hay una número infinito y como prolog intenta encontrar todas las soluciones, nunca deja de buscar, aunque estoy seguro de que golpeará una pila sobre el flujo o algún error antes :).

Una forma de limitar el número de resultados es limitar el tamaño de la solución

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

Obtiene todas las soluciones con exactamente 4 valores, lo que sería

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

creciente a 6 sería dió :

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

O uso rangos:

phrase(s, X), length(X, Y), Y >= 4 , Y < 10, Y != 6.