prolog - 过渡问题未知原因

Question

我正在尝试创建一个 NFA 来用接受“y|x*”的状态来描述它

这是我目前尝试过的:

acpt(State, [A]).
acpt(State, []) :- acpt(State).
acpt(State, InputList) :- InputList = [A],
                             transition(State, X).

当给定输入时

acpt(q0, [x,y]).

我在找它返回t

true

给予时

acpt(q0, [x,x,y]).

它应该返回

false

我的代码产生了一些错误，我想知道是否可以获得一些帮助。谢谢。

Answer 1

我评论得到需要的更正

1 ?- acpt(q0, [x,y]).
true 
.

2 ?- acpt(q0, [x,x,y]).
false.

工作代码:

% totally useless:
% acpt(State, [A|B]).

% typo: of course, we need acptng/1
% acpt(State, []) :- acpt(State).

acpt(State, []) :- acptng(State).
acpt(State, [A|B]) :-
    transition(State, X, A),
    acpt(X, B).

现在，除了测试输入正常工作之外，我必须说我看不到“epsilon 规则”的实现。 IIRC，NFA 应该允许更改状态而不消耗输入。

编辑

痕迹

4 ?- leash(-all),trace,acpt(q0, [x,x,x]).
   Call: (7) so:acpt(q0, [x, x, x])
   Call: (8) so:transition(q0, _G1431, x)
   Exit: (8) so:transition(q0, q3, x)
   Call: (8) so:acpt(q3, [x, x])
   Call: (9) so:transition(q3, _G1431, x)
   Exit: (9) so:transition(q3, q3, x)
   Call: (9) so:acpt(q3, [x])
   Call: (10) so:transition(q3, _G1431, x)
   Exit: (10) so:transition(q3, q3, x)
   Call: (10) so:acpt(q3, [])
   Call: (11) so:acptng(q3)
   Exit: (11) so:acptng(q3)
   Exit: (10) so:acpt(q3, [])
   Exit: (9) so:acpt(q3, [x])
   Exit: (8) so:acpt(q3, [x, x])
   Exit: (7) so:acpt(q0, [x, x, x])
true 
.