我為自動機撰寫了資料結構和一些函式，但我堅持使用將接受自動機物件和 k 的 find_way 函式。
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
uj5u.com熱心網友回復：
我想實作這一點的“明顯”方法是find_way使用delta在自動機中邁出一步，然后goal使用具有不同初始狀態的修改后的 FSM 遞回呼叫。當用戶詢問是否接受長度為 0 的字串時，不要忘記在某處添加基本情況。
但這種方式效率極低。我推薦一種不同的方式：
- 制作一個新型別，
type Witness a = (String, a)或類似的。這種型別的想法是，String如果您從 FSM 的初始狀態開始并使用String. - 撰寫一個函式
successors :: Ord a => FSM a -> [Witness a] -> [Witness a]，在給定一組狀態的情況下，找到從至少一個狀態的一次轉換中可以到達的所有狀態。可能有很多方法可以達到給定狀態，因此請確保對其輸出進行重復資料洗掉，Witness為每個狀態保留一個（不管是哪一個）。 - 迭代該函式
k次，從只有 FSM 的初始狀態和空字串的集合開始，然后檢查輸出和 FSM 的最終狀態中是否有任何狀態。
第一種/顯而易見的方式類似于 O(a^k)，其中 a 是字母表的大小，k 是要查詢的長度。提出的不同方式更像是 O(k*n*(a log(n)))，其中 n 是狀態的總數（a 和 k 與以前一樣）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/427306.html