2

我是 Prolog 的初学者，我想问一个关于 Prolog 的问题。

我的程序基于非确定性有限状态自动机。

起始状态为S0，最终状态为S3。

图是

在此处输入图像描述

所以如果有一个字符串[a,a,b,b,c,c]它应该像

start(s0).
edge(a, s0, s0).
edge(a, s0, s1).
edge(b, s1, s1).
edge(b, s1, s2).
edge(c, s2, s2).
edge(c, s2, s3).
final(s3).

有一个谓词accepts(Ls)if（有Ls一个字符串列表）

accepts(Ls) :- start(A), goesTo(Ls, A, B), final(B).

并假设 NFA 从状态Si到状态Sj并且在它们之间存在状态Sk，goesTo谓词定义为

goesTo(Ls, Si, Sj) :- edge (L, Si, Sk), goesTo(Ls, Sk, Sj).

但是，如果查询（从到的accepts(Ls)任意字符串列表），教程问题说它几乎肯定会进入无限搜索并且会发生堆栈溢出。ac

但是，我不明白为什么查询会进入无限搜索并导致堆栈溢出。如果你能给我一个理由，那就太好了！

（编辑：）确切的报价是：

“一个典型的 Prolog 用户可能希望他/她的 goTo 规则是这样的，即查询接受（X）会生成被上述 NFA 接受的连续字符串。几乎可以肯定，鉴于给定 NFA 的上述表示，Prolog 系统将进入无限搜索并发生堆栈溢出。说明为什么会这样。（如果您要避免此问题，请说明您如何设法避免它）。

4

3 回答 3

2

这是您的 NFA 的定义：

start(s0). 
edge(a, s0, s0). 
edge(a, s0, s1). 
edge(b, s1, s1). 
edge(b, s1, s2).
edge(c, s2, s2). 
edge(c, s2, s3).
final(s3).

它与您可能测试其接受的任何输入字符串没有任何联系。注意每行末尾的点 - 这些是定义 NFA 的 Prolog 谓词。

accepts/1使用任何 具体的输入字符串运行您的将导致有限递归。这里的搜索空间是有限的，它肯定会被耗尽——只要你accepts/1用有限长度的完全实例化的字符串调用。

现在，如果您要尝试生成所有可能的路径可接受的字符串，那么您将有无限递归，因为有无限数量的可接受的字符串：

a,b,c
a,a,b,c
a,a,a,b,c
a,a,a,a,b,c
.....

都是这个自动机可以接受的字符串。

您的谓词定义都错过了最后一个点顺便说一句。而且goesTo不太对。必须改为：

goesTo([], S, S).
goesTo([L1|Ls], S1, Sn) :- edge(L1, S1, S2), goesTo(Ls, S2, Sn).
accepts(Ls) :- start(A), goesTo(Ls, A, B), final(B).

还要注意，谓词名称和左括号之间不能有空格。

所以现在OP已经澄清了他们的问题。这是，

为什么尝试生成所有可能的可接受字符串几乎肯定会进入非生产性循环？

该调用accepts(X)确实进入了无限递归，因为要尝试的新节点的生成从头开始重新启动，因此在内部，a尝试了无限增长的 s 字符串：

a
a,a
a,a,a
a,a,a,a
....

仅仅因为edge(a,s0,s0)是edge数据库中的第一个事实，并且调用edge/3位于goesTo/3谓词定义中的第一个位置。Prolog 的搜索策略是从左到右的。

通过像这样重新安排目标，我们可以从完全非生产性行为（Prolog 只是挂在一个无限循环中）到生产性行为：

start(s0). 
edge(a, s0, s1). 
edge(b, s1, s2).
edge(c, s2, s3).
edge(a, s0, s0). 
edge(b, s1, s1). 
edge(c, s2, s2). 
final(s3).

现在，

12 ?- accepts(X).

X = [a, b, c] ;
X = [a, b, c, c] ;
X = [a, b, c, c, c] ;
X = [a, b, c, c, c, c] ;
X = [a, b, c, c, c, c, c] ;
X = [a, b, c, c, c, c, c, c] ;
X = [a, b, c, c, c, c, c, c, c]

不幸的是，可以看出这一代人倾向于c. 如何让它“公平”......让我们把它留给另一个问题，好吗？

于 2012-10-05T13:49:07.320 回答
1

因为它是其他人所说的循环。

ps 任务已经延长到这个星期四，所以不用惊慌[还] 是的，我知道你在做什么任务

于 2012-10-07T05:55:43.030 回答
1

由于 Prolog 采用的搜索策略，程序会循环。它尝试使用深度优先策略来解决探索解决方案空间的查询，即空间有效但不完整。

现在应该清楚，由于图中的这些循环，在您的情况下解决方案空间是无限的。从初始状态到最终状态有无限的路径。

迭代深化应该是枚举路径更简单的方法，在Prolog中很容易实现。另一种可能性是实施广度优先搜索。

于 2012-10-05T16:49:43.583 回答