I've been trying to make a non-deterministic finite automata in PROLOG, here is my code:
state(1).
state(2).
state(3).
initial_state(1).
final_state(3).
alphabet(a).
alphabet(b).
delta(1, b, 2).
delta(2, a, 2).
delta(2, a, 3).
delta(3, b, 2).
accept([X|[]], Q) :-
alphabet(X),
delta(Q, X, Q1),
final_state(Q1).
accept([X|XS], Q) :-
alphabet(X),
delta(Q, X, Q1),
accept(XS, Q1).
Where accept is a function that given a string and a state, it will tell us if it's accepted by the automata. The problem is that when I try to see if the string baba ([b,a,b,a]) is accepted by the automata (accept([b,a,b,a],1)) I get true, which is not right.
why do you think it should fail? The solution sequence is
delta(1, b, 2)
delta(2, a, 3)
delta(2, a, 2)
delta(2, a, 3)
My personal "best practice" is to collect the proof
accept([X|[]], Q,[delta(Q, X, Q1)]) :-
alphabet(X),
delta(Q, X, Q1),
print(delta(Q, X, Q1)),nl,
final_state(Q1).
accept([X|XS], Q,[delta(Q, X, Q1)|Rest]) :-
alphabet(X),
delta(Q, X, Q1),
print(delta(Q,X,Q1)),nl,
accept(XS, Q1,Rest).
accept(String,State):-accept(String,State,_).
this shows you that the program can be proofed with the above sequence
?- accept([b,a,b,a],1, Proof).
Proof = [delta(1, b, 2), delta(2, a, 3), delta(3, b, 2), delta(2, a, 3)]