主页 / user-435351

user435351's questions

Martin Hope
user435351
Asked: 2022-04-21 23:06:53 +0800 CST
  • 0

如何在prolog中找到一个接受非确定性有限自动机的长度为k的单词（如果有很多，一个就足够了）？我这样写机器：

states([q0, q1, q2]).
symbols([a, b]).
transition(q0, a, q1).
transition(q0, b, q2).
transition(q1, a, q2).
transition(q1, b, q0).
transition(q2, a, q1).
transition(q2, b, q2).
startState(q0).
finalStates([q2]).
prolog
Martin Hope
user435351
Asked: 2022-03-22 18:41:36 +0800 CST
  • 3

我需要检查自动机是否允许包含相同字符的单词。如果至少存在一个，则打印它，如果不存在，则打印“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