检查它是否接受至少一个长度为 k 的有限行列式自动机，如果是 - 打印它，否则 - 打印 "No"

Question

我为自动机编写了数据结构和一些函数，但我坚持使用 find_way 接受自动机对象和 k 的函数。

type FSM q = ([q], Alphabet, [Transition q], q, [q])
type Alphabet = [Char]
type Transition q = (q, Char, q)

states :: FSM q -> [q]
states (u, _, _, _, _) = u

alph :: FSM q -> Alphabet
alph (_, a, _, _, _) = a
trans :: FSM q -> [Transition q]
trans (_, _, t, _, _) = t
start :: FSM q -> q
start (_, _, _, s, _) = s
final :: FSM q -> [q]
final (_, _, _, _, f) = f

--return a or Nothing if no transition found
delta :: Eq a => FSM a -> a -> Char -> Maybe a
delta m st symbol = listToMaybe [q1 | (q0, x, q1) <- trans m, q0 == st, x == symbol]

--return "No" or first accepted word found
    
goal:: Eq a => FSM a -> Int -> String
goal m k = fromMaybe "No" $ asum [find_way m k x | x <- alph m]

find_way :: Eq a => FSM a -> Int -> Char -> Maybe String

Answer 1

我想实现这个的“明显”方法是 find_way 使用 delta 在自动机中迈出一步，然后递归调用 goal 使用修改后的 FSM不同的初始状态。当用户询问是否接受长度为 0 的字符串时，不要忘记在某处添加基本情况。

但这种方式效率极低。我推荐一种不同的方式：

创建一个新类型，type Witness a = (String, a) 或类似的。这种类型的想法是，该对包含 String 以及如果您从 FSM 的初始状态开始并使用 String.
编写一个函数 successors :: Ord a => FSM a -> [Witness a] -> [Witness a]，给定一组状态，找到从至少其中一个状态的一次转换中可以到达的所有状态。可能有很多方法可以达到给定的状态，因此请确保 de-duplicates 它的输出，每个状态只保留一个 Witness（哪个不重要）。
迭代该函数 k 次，从只有 FSM 的初始状态和空字符串的集合开始，然后检查输出和 FSM 的最终状态中是否有任何状态。

first/obvious 方式类似于 O(a^k)，其中 a 是字母表的大小，k 是要查询的长度。提议的不同方式更像是 O(k*n*(a+log(n))) ，其中 n 是状态总数（a 和 k 与之前一样）。

检查它是否接受至少一个长度为 k 的有限行列式自动机，如果是 - 打印它，否则 - 打印 "No"

Check whether it accepts a finite determinant automaton at least one word of length k, if so - print it, else - print "No"

haskell

automata