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