从初始状态开始返回DFA中的所有可达状态

Question

我试图在Haskell中编写一个程序，该程序返回从初始状态开始的可达状态列表，类似于深度优先搜索。

states_reachable :: Eq st => DFA st -> [st] 
states_reachable (qs, sigma, delta, s, inF) = 
    [delta q a | q <- qs, a <- sigma] 

注：

• 适量是状态集合
• 西格玛的是字母表
• 增量是，需要一个状态和一个符号和一个过渡函数返回下一个状态
• 小号是初始状态
• INF是如果状态是接受状态，则返回true的函数，否则为假

作为功能现在被定义：

[delta q a | q <- qs, a <- sigma] 

返回DFA中的所有状态（这是不正确的）。

我想通过从初始状态s开始填充列表并测试每个输入的delta函数。

例如：

// returns the states reachable from the initial state for all symbols in sigma 
[delta s a | a <- sigma] 

下一个步骤将是重复该过程为每个新状态加入到列表中。这可能会添加重复项，但我可以稍后删除它们。

然后我尝试：

[delta q a | q <- [delta s a | a <- sigma], a <- sigma] 

我想这可能会奏效，但它并不因为它创建内部列表，然后用它来填充外部列表，然后停止。

我需要通过探索delta函数返回的所有新状态递归构建此列表。

Answer 1

您正试图计算关系的传递闭包，其中关系是“x可以一步到达y”。因此，我建议使用通用传递闭包解决方案，而不是DFA特定解决方案，然后从您的DFA中生成该关系。这里有一个相当基本的方式来做到这一点：

module Closure (closure) where             
import Data.List (nub) 

closure :: Eq a => (a -> [a]) -> a -> [a] 
closure nexts init = go [init] 
    where go xs = let xs' = nub $ xs ++ (xs >>= nexts)        
       in if xs == xs'             
        then xs              
        else go xs'             

这里的算法是有到达状态的列表，然后在每一步从每个到其所有的近邻散步展开它，然后nub列表中摆脱重复。一旦该扩展步骤不添加新节点，就完成了。

现在，如何将DFA问题映射到此问题上？这并不难：您只需使用sigma和delta即可生成nexts函数。在这里，我们需要假设您的DFA delta函数是全部的，即每个节点都有一个针对sigma中的每个字母指定的转换。这很容易创建一个额外的“故障”节点，所有节点可以过渡到，如果他们不喜欢他们的输入，所以我会假设已经完成。

neighbors :: (node -> letter -> node) -> [letter] -> node -> [node]    
neighbors delta sigma n = map (delta n) sigma         

有了到位，原来的问题简化为：

closure (neighbors delta sigma) s