在 prolog 中构建 FSA

Question

我被要求在序言中代表 FSA。

一个 fsa 是一个状态列表。
一个状态是一个结构体，具有仿函数状态和 3 个参数：一个名称，一个列表转换，是或否以指示状态是否正在接受或没有。
转换是一种具有仿函数转换和 2 个参数的结构：from、一个角色，一个州名。

我们的 FSA 没有 epsilon 动作。

如果 FSA 是不确定的，

nondfsa(FSA) 为真。完成 nondfsa。提示：使用一个辅助谓词，nondstate(State)，如果 State 具有不确定性，则为真过渡。您可以为谓词添加子句。`

我得到的答案如下：

nondfsa([Hstate | _ ])
    :- nondstate(Hstate).
nondfsa([ _ | Tailstates]) :-
    nondfsa(Tailstates).

nondstate(state( _ , Transitions, _ )):-
    member(transition(Char, To1), Transitions),
    member(transition(Char, To2), Transitions),
    not(To1 = To2).

谁能帮我解释一下每个谓词在做什么？我很困惑这些行到底要翻译成什么。

我理解如果至少一个状态具有多个具有相同特征的转换，则没有 epsilon 移动的 fsa 是不确定的。我只是不明白这段代码是怎么回事。

Answer 1

提供的代码非常简单，学习 "read through" Prolog 谓词会很好。

nondfsa([Hstate | _ ]) :-
    nondstate(Hstate).
nondfsa([ _ | Tailstates]) :-
    nondfsa(Tailstates).

这是一种非常常见的 Prolog 模式，它递归地检查列表的每个元素。 nondfsa/1 检查列表的每个元素。如果其中任何是非确定性状态（根据 nondstate/1），则 nondfsa/1 成功，这意味着 FSA 是非确定性的。如果 nondstate/1 对给定列表中的 any 元素不成功，则 nondfsa/1 将失败。第一个子句检查列表的头部。第二个子句跳过头部并检查列表的其余部分。在递归调用中，Prolog 再次从第一个子句开始，因此它只是通过 nondstate/1.

检查下一个元素

nondstate(state( _ , Transitions, _ )):-
    member(transition(Char, To1), Transitions),
    member(transition(Char, To2), Transitions),
    not(To1 = To2).

nondstate/1 如果发现给定的 state/3 根据某些仅取决于该状态转换的定义是不确定的，则

nondstate/1 成功。如果您通读 nondstate/1 谓词，就会明白这是什么。如果满足以下条件，则谓词成功：

我可以获得转换列表的成员
我可以使用相同的字符获得转换列表的另一个成员（这将至少成功一次，使用与#1 中相同的成员）
两个成员的目的地状态不同

换句话说，如果有一个角色至少过渡到两个不同的状态，则状态是不确定的。

在 prolog 中构建 FSA

building FSA in prolog

prolog

finite-automata