在prolog建设FSA

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

fsa是一个状态列表。

状态是一个具有仿函数状态和3个参数的结构：一个名称，一个过渡列表，以及yes或no来表示状态是否接受。

转换是一个带有仿函数转换和2个参数的结构：从，一个字符和一个状态名称。

我们的FSA没有epsilon动作。

如果FSA是非确定性的， nondfsa(FSA)是正确的。 完成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是非确定性的。 我只是不明白这段代码发生了什么。

---

所提供的代码非常简单，学会“通读”一个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谓词nondstate/1谓词，你可以看到它是什么。 谓词成功，如果：

我可以获得转换列表的成员

我可以使用相同的角色获得转换列表中的另一个成员（这将总是成功至少一次，使用与＃1中相同的成员）

两个成员中每一个的目标状态都不相同

换句话说，如果有一个角色已经转换到至少两个不同的状态，那么状态是非确定性的。

链接地址: http://www.djcxy.com/p/66941.html

上一篇: building FSA in prolog

下一篇: declarative Horn logic?