Prolog 中的有限状态自动机

Question

Prolog 中的程序描述一个有限的 automata.It 需要有 2 个参数列表，例如第一个包含输入 ([a,b,a,b,a])，另一个是输出，它应该return through whitch states it has been through, following the arrows, example [1,3,2,4,5]

Answer 1

假设您使用谓词 f(StartState, EdgeLabel, EndState):

对有限状态自动机进行编码

f(1,a,2).  f(1,b,1).
f(2,a,3).  f(2,b,4).
f(3,a,5).  f(3,b,2).
f(4,a,5).  f(4,b,1).
f(5,a,3).  f(5,b,1).

只需将查询链接到 f/3:

，即可针对固定的操作顺序回答此问题

?- X1=1, f(X1,a,X2), f(X2,b,X3), f(X3,a,X4), f(X4,b,X5), f(X5,a,X6), L=[X1,X2,X3,X4,X5,X6].
L = [1, 2, 4, 5, 1, 2] .

可以递归地回答针对一系列操作的相同查询。

基本步骤很简单：如果您从 Start 开始，并且不应用任何操作 ([])，则访问状态为 [Start].

walk(Start, [], [Start]).

如果您有一系列动作和一系列访问状态，我们从 Start 应用动作 Input 并到达状态 State，并递归执行相同的操作剩余动作 Inputs 和剩余状态 States:

walk(Start,[Input|Inputs],[Start|States]) :-
    f(Start,Input,State),
    walk(State, Inputs, States).

测试：

?- walk(1, [a,b,a,b,a], X).
X = [1, 2, 4, 5, 1, 2] ;
false.

Prolog 中的有限状态自动机

Finite State Automata in Prolog

prolog

state-machine