Mini-aplicación: NDFA

Representación: trans(Edo1, Simbolo, Edo2)., trans_vacio(Edo1,Edo2).,
final(Edo).

acepta(Edo,[]) :-
    final(Edo).
acepta(Edo,[H|T]) :-
    trans(Edo,H,NEdo),
    acepta(NEdo,T).
acepta(Edo,String) :-
    trans_vacio(Edo,NEdo),
    acepta(NEdo,String).

e.g., 
trans(s1,0,s1).      trans(s1,1,s2).
trans(s1,0,s4).      trans(s2,0,s2).
trans(s2,0,s3).      trans(s3,1,s5).
trans_vacio(s4,s2).  final(s5).

?- acepta(s1,[0,1,0,1]).
yes
?- acepta(X,[0,0,1]).
X = s1;
X = s2;
X = s4
?- acepta(s1,[X,Y,Z]).
X = 1, Y = 0, Z = 1;
X = 0, Y = 0, Z = 1

?- Sol = [_,_,_], acepta(s1, Sol).
Sol = [1,0,1];
Sol = [0,0,1]

Si le ponemos un ciclo de transiciones vacías entonces podemos caer en loops infinitos si el string que se le da no es una solución (y en ciertos casos, aunque sea una solución): e.g., trans_vacio(s2,s4). y ?- acepta(s1,[1]).