prolog - 在序言中构建 FSA

Question

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

• fsa 是一个州列表。
• 状态是一个具有仿函数状态和 3 个参数的结构:名称、列表 转换，以及 yes 或 no 来指示状态是否正在接受或 不。
• 转换是一个具有仿函数转换和 2 个参数的结构:from、 一个字符，to 一个州名。

我们的 FSA 没有 epsilon 移动。

如果 FSA 不确定，则

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

我得到的答案如下:

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

所提供的代码非常简单，学习“通读”Prolog 谓词会很好。

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

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

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

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

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

1. 我可以获得转换列表中的一个成员
2. 我可以使用相同的字符获取转换列表中的另一个成员(使用与 #1 中相同的成员，这将始终成功至少一次)
3. 两个成员的目的地州不同

换句话说，如果一个角色已经转换到至少两种不同的状态，则状态是不确定的。