prolog - 自动机和序言

Question

我一直在尝试在 PROLOG 中制作一个非确定性有限自动机，这是我的代码:

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).

其中 accept 是一个函数，它给出一个字符串和一个状态，它会告诉我们它是否被自动机接受。
问题是，当我尝试查看字符串 baba ([b,a,b,a]) 是否被自动机接受 (accept([b,a,b,a],1)) 时，我得到了 true，即是不正确的。

Answer 1

为什么你认为它应该失败？
求解顺序为

delta(1, b, 2)
delta(2, a, 3)
delta(2, a, 2)
delta(2, a, 3)

我个人的“最佳实践”是收集证明

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,_).

这表明您可以使用上述序列证明该程序

?- accept([b,a,b,a],1, Proof).
Proof = [delta(1, b, 2), delta(2, a, 3), delta(3, b, 2), delta(2, a, 3)]