主页 / 问题 / 1259211
Accepted
user435351
Asked:2022-03-22 18:41:36 +0000 UTC2022-03-22 18:41:36 +0000 UTC

在 Haskell 中实现自动机算法

  • 772

我需要检查自动机是否允许包含相同字符的单词。如果至少存在一个，则打印它，如果不存在，则打印“NO”。对于输入字母表中的每个字符，我们运行一个搜索，如果我们来到最后一个阵营，我们必须打印这个单词。如果我们在最后一个阵营中没有命中两次，则停止搜索特定字母（我们进入了一个循环）。我写了部分代码，创建了一个自动机类型，但我不知道如何在 Haskell 中实现算法本身。

main = do { 
print(goal m1);
print(goal m2);
print(goal m3);
print(goal m4);
}

w = "abab" 
type FSM q = ([q], Alphabet, [Transition q], q, [q]) 
type Alphabet = [Char] 
type Transition q = (q, Char, q) 
 
     
m1 :: FSM Int 
m1 = ([0, 1, 2, 3], 
      ['a', 'b'], 
      [(0, 'a', 1), (1, 'a', 3), (2, 'a', 2), 
       (0, 'b', 2), (2, 'b', 3), (1, 'b', 1)], 
      0, 
      [3] 
    ) 
 
m2 :: FSM Int 
m2 = ([0, 1, 2, 3], 
      ['a', 'b'], 
      [(0, 'a', 1), (1, 'a', 3), (2, 'a', 2), 
       (0, 'b', 2), (2, 'b', 3), (1, 'b', 1), 
       (3, 'a', 3), (3, 'b', 3)], 
      0, 
      [3] 
    ) 
 
m3 :: FSM Int 
m3 = ([0, 1, 2, 3], 
      ['a', 'b'], 
      [(0, 'a', 1), (1, 'a', 3), (2, 'a', 2), 
       (0, 'b', 2), (2, 'b', 3), (1, 'b', 1), 
       (3, 'a', 1), (3, 'b', 3) ], 
      0, 
      [3] 
    ) 

m4 :: FSM Int 
m4 = ([0, 1, 2, 3, 4, 5], 
      ['a', 'b'], 
      [(0, 'a', 1), (1, 'a', 2), (2, 'a', 3), 
       (3, 'a', 5), (5, 'a', 4), (1, 'b', 1), 
       (3, 'b', 1), (3, 'b', 3) ], 
      0, 
      [4] 
    ) 
 
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

delta :: FSM Int -> Int -> Char -> Int 
delta m st symbol | length [q1 | (q0, x, q1) <- trans m, q0 == st, x == symbol] > 0 = [q1 | (q0, x, q1) <- trans m, q0 == st, x == symbol] !! 0 | otherwise = -1

goal:: FSM Int -> String
goal m = seek m (alph m) where
    seek m [] = "No"
    seek m (x:xs) | find_letter m x > 0 = create_word x (find_letter m x) [] | otherwise = seek m xs


find_letter:: FSM Int -> Char -> Int 
find_letter m s = dfs m s (start m) [start m] 0 where
    dfs m s state states count 
        | (delta m state s) elem states = 0 
        | (delta m state s) == -1 = 0 
        | (delta m state s) elem (final m) = count + 1
        | otherwise = dfs m s (delta m state s) (states++[delta m state s]) (count+1)
 
create_word:: Char -> Int -> [Char] -> [Char]
create_word symbol 0 list = list
create_word symbol count list = create_word symbol (count-1) (list++[symbol])
haskell

1 个回答

  1. Best Answer

    问题简化为在有向图中寻找路径。例如，对于您的情况m1 在此处输入图像描述

    您需要找到从初始状态（ type 的第四个字段FSM） - 图上的顶点0到最终状态之一（ type 的第五个字段FSM）的路径之一，在这种情况下它是一个 - 这是顶点3。在这种情况下，仅使用标记相同的边，例如 onlya或 only b。

    那些。算法将是这样的

    • 我们以字母表中的一个字符为例，a
    • 删除所有标有其他符号的边。 在此处输入图像描述
    • 寻找从顶点0到顶点的路径3（例如，广度优先搜索）

    在这种情况下，它将是通过两条边的路径 0→1→3 a，这意味着自动机允许至少一个合适的字符串 -aa

    如果找不到路径，请对其他最终状态和剩余字符重复这些步骤。

    编辑问题后的附录

    如果你不改变你的算法，它会变成这样

    import Data.Maybe (fromMaybe, listToMaybe)
import Data.Foldable (asum)
...

delta :: Eq a => FSM a -> a -> Char -> Maybe a
delta m st symbol = listToMaybe [q1 | (q0, x, q1) <- trans m, q0 == st, x == symbol]

goal :: Eq a => FSM a -> String
goal m = fromMaybe "No" $ asum [flip replicate x <$> find_letter m x | x <- alph m]

find_letter :: Eq a => FSM a -> Char -> Maybe Int
find_letter m s =  dfs (start m) [start m] 1
  where
    dfs state seen count =
      case delta m state s of
        Nothing -> Nothing
        Just nextState
          | nextState `elem` seen -> Nothing
          | nextState `elem` final m -> Just count
          | otherwise -> dfs nextState (nextState : seen) (count + 1)

    但请记住，在最初的问题中，您有一个不确定的自动机m4，并且由于显而易见的原因，算法将无法工作。

    就我自己而言，我可以提供这个选项：由于有效单词中的最小字符数不能超过状态数，您可以简单地一次向机器输入一个字母，直到我们达到最终状态或直到我们超过节点。

    这是一个非确定性自动机的例子。

    m4 :: FSM Int
m4 = ([0,1,2,3,4,5,6,7],
      ['a', 'b'],
      [(0,'a',1), (1,'b',1), (1,'a',4), (0,'a',3),
      (0,'b',2), (3,'b',2), (2,'b',5), (5,'a',5),
      (4,'b',6), (5,'a',6), (6,'b',3), (3,'a',5),
      (6,'a',7), (7,'b',7), (7,'a',4)],
      0,
      [7])

next :: Eq a => FSM a -> Char -> a -> [a]
next m char st = [to | (from, x, to) <- trans m, x == char, st == from]

    GHCi> take (length (states m4)) $ iterate (nub . (>>= next m4 'a')) [start m4]
[[0],[1,3],[4,5],[5,6],[5,6,7],[5,6,7,4],[5,6,7,4],[5,6,7,4]]
GHCi> take (length (states m4)) $ iterate (nub . (>>= next m4 'b')) [start m4]
[[0],[2],[5],[],[],[],[],[]]

    对于一个字母，在第五步达到a最终状态7，这意味着单词中有4个字母a。对于一封信，b未达到最终状态。

    • 3

相关问题