list - resueltos - gramatica libre de contexto palindromo

escritura contexto gramática libre en prólogo

Question

digamos que tuve la siguiente gramática libre de contexto.

S -> A
A -> mAn
A -> o

¿Cómo se vería esto en Prolog? Esto es lo que intenté, pero no funciona. La segunda línea parece ser el problema.

S(Z) :- A(Z).
A(Z) :- append([m],X,Z2), A(X), append(Z2,[n],Z).
A([o]).

Answer 1

En esta respuesta, usamos el predicado append/3 disponible comúnmente append/3 .

s(Xs) :- a(Xs). a([o]). a([m|Xs]) :- append(Xs0,[n],Xs), a(Xs0).

Consulta de muestra:

?- length(Xs,_), s(Xs). Xs = [o] ; Xs = [m,o,n] ; Xs = [m,m,o,n,n] ; Xs = [m,m,m,o,n,n,n] ...

NOTA: Usar append/3 lugar de dcg es, en general, una mala elección y puede contribuir a un menor rendimiento del tiempo de ejecución y a la legibilidad del código. Siempre que sea posible, use dcg en su lugar!

Answer 2

ya que la gramática no se deja recursiva, podemos usar un DCG :

s --> a.
a --> [m], a, [n].
a --> [o].

entonces podemos analizar o generar todas las secuencias aceptadas. Por ejemplo, generar:

?- length(L, _), phrase(s, L).
L = [o] 
L = [m, o, n] 
L = [m, m, o, n, n] 
...

para inspeccionar el código de Prolog:

?- listing(s).
s(A, B) :-
    a(A, B).

?- listing(a).
a([m|A], C) :-
    a(A, B),
    B=[n|C].
a([o|A], A).

no se requiere agregar / 3, gracias a las listas de diferencias

editar usando append / 3

s(Z) :- a(Z).
a(Z) :- append([m|X],[n],Z), a(X).
a([o]).

SWI-Prolog tiene append / 2 (simplemente basado en append / 3 correctamente encadenado), que da una alternativa más legible

a(Z) :- append([[m],X,[n]], Z), a(X).

de todos modos, debemos llamar a / 1 recursivamente después de que la lista haya sido construida / dividida