自动机和序言

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)

我个人"best practice"是去取证

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

自动机和序言

Automata and prolog

prolog

finite-automata