prolog - 我无法理解 Prolog 如何知道 DFA 接受规则中的开始状态

Question

我用我能想到的最好的方式来措辞标题，但让我说清楚。在 Prolog 中编写 DFA 时，这是一种典型的做法:

start(q0).
final(q2).

transition(q0, a, q1).
transition(q1, b, q1).
transition(q1, c, q2).

accept(Symbols) :- start(StartState), accept(Symbols, StartState).

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

accept([Symbol|Symbols], State) :- transition(State, Symbol, NextState), 
                                accept(Symbols, NextState).

我理解这段代码的作用、目标是什么等等。让我感到困惑的是“接受”规则。同样，我了解正在执行的操作背后的逻辑，但我不了解的是 StartState 和 NextState 的突然使用。这些只是无处不在，我不明白 start(StartState) 甚至会返回 true 开始，更不用说值(value)的来源了。使用 NextState 也是一样。 Prolog“认为”这些值是什么以及它们如何被转换事实所接受？

如果我从事实开始:start(q0).，那么 start(StartState) 是怎样的。真的吗？

Answer 1

虽然 mat 的回答是正确的，但我将在此处为您提供一些操作语义，即如何它是如何发生的。

你问，“如果我从事实开始:start(q0).，那么 start(StartState). 怎么会是真的？”

回答:StartState 是一个逻辑变量。它还没有为它设置任何值。是我们写下了这个名字，“不知从何而来”——它可以是我们选择的任何名字； Prolog 看到它，看到它是一个新名称(以大写字母开头)，并使用该名称创建一个新的 logvar，该名称尚未实例化(分配一个值)。它就像一个 NULL 指针，以后只能一次设置(除非系统回溯，但这是一个正交问题)。

这就是 Prolog 的工作原理:它看到一个查询，start(X)；它看到 X 是一个新的 logvar；现在它试图证明这个查询。这意味着，它会在所有已知事实和规则中搜索与我们的查询匹配的head。

有一个:它是事实 start(q0)。注意 q0 以小写字母开头。这意味着它是一个原子，一个符号数据。变量以大写字母开头。

Prolog 如何找到事实 start(q0)？就是这样。这是给定 Prolog 实现的细节。它在构成我们编写的程序的所有事实和规则中找到它，并加载到 Prolog 中。

现在系统将 start(q0) 与 start(X) 匹配。这称为统一:

start(q0) = start(X)

这成功了，X = q0。 logvar X 被赋值，匹配成功。因此，使用替换 { X = q0 } 证明了查询。

这就是 Prolog 的工作原理。

但实际上，您应该阅读一个好的 Prolog 教程，以便您理解上面所有的 斜体 单词。之后还会有更多问题需要学习，因此您最终可以确信自己“理解”了 Prolog。