在Haskell中的有限自动机

Question

如何在Haskell中表示有限自动机？它的数据类型会是什么样子？

在我们学院，自动机被定义为一个5元组

(Q, X, delta, q_0, F)

其中Q为自动机的状态集，X是字母表（这部分是否必要尚不确定），delta是从（Q，X）取2元组并返回状态/-s（在非确定性版本中）的转移函数，F是接受/结束状态的集合。

最重要的是，我不确定delta应该具有什么类型...

- mathemage

---

对于确定性自动机，delta 可以是 Q -> X -> Q 类型的。对于非确定性自动机，我会选择类似 Q -> X -> [Q] 的形式。 - Sven Hager

Sven Hager所说的，以及F可以实现为isEnd :: Q -> Bool。 - Sjoerd Visscher

Answer 1

有两种基本选项：

• 像Sven Hager建议的那样，使用显式函数delta :: Q -> X -> Q（或适当的[Q]）。
• 使用映射delta :: Map (Q, X) Q，例如使用Data.Map，或者如果您的状态/字母表可以按升序编号，则使用Data.Array或Data.Vector。

请注意，这两种方法本质上是等效的，可以相对容易地从映射版本转换为函数版本（由于lookup调用中的额外Maybe略有不同）。

delta_func q x = Data.Map.lookup (q,x) delta_map

(或者使用适合您使用的映射类型的经过适当柯里化的查找函数版本。)

如果您在编译时构造自动机（因此知道可能的状态并将其编码为数据类型），则使用函数版本可以提供更好的类型安全性，因为编译器可以验证您是否已覆盖所有情况。

如果您在运行时构造自动机（例如从用户输入），则将 delta 存储为映射（并可能执行如上的函数转换）并具有适当的输入验证以保证正确性，使得 fromJust 是安全的（即对于任何可能的 (Q,X) 元组，该映射都有一个条目，因此查找永远不会失败（永远不会返回 Nothing））。

非确定性自动机与映射选项配合使用效果很好，因为失败的查找与没有状态可转换相同，即一个空的 [Q] 列表，因此不需要对 Maybe 进行任何特殊处理，除了调用 join . maybeToList（join 来自 Data.Monad，maybeToList 来自 Data.Maybe）。

另外，字母表绝对是必需的：这是自动机接收输入的方式。

- huon

---

非常感谢你提供如此全面的答案 :-)我还有一个问题：在将正则表达式转换为自动机时，表示 delta 的更好方法是什么？我需要实现自动机的操作，例如串联、分离和迭代。在我看来，使用 map 是最好的选择 - 或者我错了吗？ - mathemage

@mathemage，你可以尝试实现两种方法并看看哪个更适合你（我建议先尝试使用map版本）。此外，如果这个答案对你有帮助，你应该投票支持它，如果它回答了你的问题，你可以用勾号表示接受：faq中有更多细节。 - huon

@mathemage：如果您使用自动机箭头（请参阅下面我的完整答案），那么我认为您可以用组合函数来表达这些操作。例如，析取将是一个函数，它将输入传递给其两个参数状态，并返回一个新函数，该函数是两个结果的析取。 - Paul Johnson

Answer 2

请查看“arrows”包中的Control.Arrow.Transformer.Automaton模块。类型如下：

newtype Automaton a b c = Automaton (a b (c, Automaton a b c))

这有点令人困惑，因为它是一个箭头变换器。在最简单的情况下，你可以写成：

type Auto = Automaton (->)

这里使用函数作为基础箭头。在自动机定义中用(->)代替"a"，并使用中缀符号可以看出它大致等同于：

newtype Auto b c = Automaton (b -> (c, Auto b c))

换句话说，自动机是一个函数，它接受输入并返回结果和新的自动机。

您可以直接使用它，编写每个状态的函数，该函数接受参数并返回结果和下一个函数。例如，这里有一个状态机来识别正则表达式"a+b"（即至少由一个'a'后跟一个'b'的系列）。 （注意：未经测试的代码）

state1, state2 :: Auto Char Bool
state1 c = if c == 'a' then (False, state2) else (False, state1)
state2 c = case c of
              'a' -> (False, state2)
              'b' -> (True, state1)
              otherwise -> (False, state1)

关于你最初的问题，Q = {state1, state2}，X = Char，delta 是函数应用，F 是状态转换返回True的输出转换（而不是使用“接受状态”，我使用了一个具有接受值的输出转换）。

或者你可以使用箭头符号。自动机是所有有趣的箭头类的实例，包括Loop和Circuit，因此您可以通过使用delay来访问先前的值。（注意：再次未经测试的代码）

recognise :: Auto Char Bool
recognise = proc c -> do
   prev <- delay 'x' -< c   -- Doesn't matter what 'x' is, as long as its not 'a'.
   returnA -< (prev == 'a' && c == 'b')

“延迟”箭头表示“prev”等于“c”的先前值而不是当前值。您还可以通过使用“rec”访问以前的输出。例如，这是一个随时间衰减的总数的箭头。（实际上在这种情况下进行了测试）

-- | Inputs are accumulated, but decay over time. Input is a (time, value) pair.
-- Output is a pair consisting
-- of the previous output decayed, and the current output.
decay :: (ArrowCircuit a) => NominalDiffTime -> a (UTCTime, Double) (Double, Double)
decay tau = proc (t2,v2) -> do
      rec
         (t1, v1) <- delay (t0, 0) -< (t2, v)
         let 
            dt = fromRational $ toRational $ diffUTCTime t2 t1
            v1a = v1 * exp (negate dt / tau1)
            v = v1a + v2
      returnA -< (v1a, v)
   where
      t0 = UTCTime (ModifiedJulianDay 0) (secondsToDiffTime 0)
      tau1 = fromRational $ toRational tau

请注意，"delay"的输入包括从其输出派生的值"v"。 "rec"子句使这成为可能，因此我们可以建立反馈回路。

- Paul Johnson