1

下面的 Prolog 程序模拟了一个非确定性自动机：

final(s3).

trans(s1,a,s2).
trans(s1,b,s1).
trans(s2,b,s3).
trans(s3,b,s4).

silent(s2,s4).
silent(s3,s1).

accepts(State,[]) :- final(State).

accepts(State, [X|Rest]) :- trans(State,X,State1),
                            accepts(Stat1,Rest).

accepts(State, Rest) :- silent(State, State1),
                        accepts(State1, Rest).

好的，我有 3 种不同的事实：

第一个告诉我s3是最终状态（接受状态）。事实的第二种类型指定了读取字符串字符的自动机的转换。

例如：如果我处于状态 s1 并且读取了字符 a，那么它可以传递到状态 s2。

第三个指定空转换：即从一个状态到另一个不需要输入字符的状态的任意转换。

例如：

silent(s2,s4)

指定自动机可以在不读取任何内容的情况下任意从 s2 传递到 s4。

好的，现在我有了规则，指定如何从一个状态传递到另一个状态，以及它是否是一个接受状态。

第一个问题是：

accepts(State,[]) :- final(State).

它说：如果该状态是最终状态，则从状态接受空字符串[]。

第二条规则是：

accepts(State, [X|Rest]) :- trans(State,X,State1),
                            accepts(State1,Rest).

说：它不是空的字符串，并且如果读取字符串的第一个符号 X 自动机可以传递到某个状态 State1 并且字符串的其余部分从 State1 接受，则它从当前状态 State 接受。

第三条规则是：

accepts(State, Rest) :- silent(State, State1),
                        accepts(State1, Rest).

它说：如果自动机可以从当前状态 State 静默移动到另一个状态 State1 并且状态 State1 可以接受整个输入字符串，则从 State 接受字符串。

因此，如果在 Prolog shell 中，我执行以下语句：

accepts(s1,[a,a,a,b]).

回复是真的

但是，究竟是什么意思？

这意味着 s1 状态接受 [a,a,a,b] 字符串，因为我将自动机从初始状态 s1 带到接受状态 s3 的许多转换？

第二个疑问与书中显示的示例有关。

在书中执行此查询（获取从 s1 到最终状态 s3 的所有 3 个字符的序列）并获得以下输出：

?- accepts(s1, [X1,X2,X3]).

X1 = a
X2 = a
X3 = b;

X1 = b
X2 = a
X3 = b;

no

这是合理的，但如果我尝试在我的 Prolog shell 上执行它，我会得到这个输出：

11 ?- accepts(s1, [X1,X2,X3]).
X1 = X2, X2 = a,
X3 = b ;
X1 = X3, X3 = b,
X2 = a ;
false.

为什么？

4

1 回答 1

2

首先，当我查阅您的代码（变量名Stat1）时，我会收到一个单例变量警告。当我更正它时，该列表[a,a,a,b]（正确地，假设您声明的转换）不再被接受。此外，我稍微重写了您的代码，以便将最终状态纳入关系：

automaton(State, State, []) :- final(State).
automaton(State0, State, [X|Xs]) :-
        trans(State0, X, State1),
        automaton(State1, State, Xs).
automaton(State0, State, Rest) :-
        silent(State0, State1),
        automaton(State1, State, Rest).

变量命名方案Var0, Var1, ..., Var，其中Var0表示某些上下文中的初始状态并Var表示最终状态，是在 Prolog 中描述状态转换时通常有用的命名模式。您现在可以使用此关系来查看自动机中达到了哪个最终状态（在您的示例中，它当然始终是唯一的最终状态s3）：

?- automaton(s1, State, Xs).
State = s3,
Xs = [a, b] ;
State = s3,
Xs = [a, b, a, b] ;
State = s3,
Xs = [a, b, a, b, a, b] .

对于您的最后一个问题：是的，您是正确的，答案在声明上是等效的，SWI Prolog 只是以不同的方式编写它们（X = a, Y = a声明上等同于X = Y, X = a）。

编辑：您可以概括这个想法：在下面的代码中，我使用 DCG 来描述导致最终状态的状态转换序列：

automaton(State, []) --> { final(State) }.
automaton(State0, [X|Xs]) -->
        [{State0,X}->State1],
        { trans(State0, X, State1) },
        automaton(State1, Xs).
automaton(State0, Rest) -->
        [State0->State1],
        { silent(State0, State1) },
        automaton(State1, Rest).

例子：

?- length(Xs, _), phrase(automaton(s1, Xs), Ts).
Xs = [a, b],
Ts = [ ({s1, a}->s2), ({s2, b}->s3)] ;
Xs = [b, a, b],
Ts = [ ({s1, b}->s1), ({s1, a}->s2), ({s2, b}->s3)] ;
Xs = [a, b, a, b],
Ts = [ ({s1, a}->s2), ({s2, b}->s3), (s3->s1), ({s1, a}->s2), ({s2, b}->s3)] .
于 2013-03-31T21:00:47.803 回答