20

在 Haskell 中表示有限自动机的好方法是什么?它的数据类型如何?

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

(Q, X, delta, q_0, F)

其中 Q 是自动机状态的集合,X 是字母表(这部分是否必要),delta 是从 (Q,X) 获取 2 元组并返回 state/-s 的转换函数(在非确定性版本中)和F 是接受/结束状态的集合。

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

4

2 回答 2

18

有两个基本选项:

  • Sven Hager 建议的显式函数delta :: Q -> X -> Q(或[Q]视情况而定)。
  • 一张地图,delta :: Map (Q, X) Q例如使用Data.Map,或者如果您的州/字母表可以通过升序数字Data.ArrayData.Vector.

请注意,这两种方法本质上是等价的,可以相对容易地从地图版本转换为函数版本(由于调用的额外内容,这略有不同Maybelookup

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

(或者对于您使用的任何映射类型,查找函数的适当柯里化版本。)


如果您在编译时构建自动机(因此知道可能的状态并可以将它们编码为数据类型),那么使用函数版本可以为您提供更好的类型安全性,因为编译器可以验证您是否已涵盖所有情况。

如果您在运行时构建自动机(例如从用户输入),则存储delta为映射(并可能进行上述函数转换)并进行适当的输入验证以保证正确性,这样fromJust是安全的(即总是有一个在映射中输入任何可能的(Q,X)元组,因此查找永远不会失败(永远不会返回Nothing))。

非确定性自动机与 map 选项配合得很好,因为查找失败与没有状态可去,即空[Q]列表相同,因此不需要对调用之外的任何特殊处理Maybejoin . maybeToListjoin是从Data.MonadmaybeToList是从Data.Maybe)。


另一方面,字母表绝对是必要的:它是自动机接收输入的方式。

于 2012-06-16T14:29:06.417 回答
13

查看“箭头”包中的 Control.Arrow.Transformer.Automaton 模块。类型看起来像这样

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

这有点令人困惑,因为它是一个箭头转换器。在最简单的情况下,您可以编写

type Auto = Automaton (->)

它使用函数作为底层箭头。用 (->) 代替 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 的状态转换(而不是“接受状态”,我使用了带有接受值)。

或者,您可以使用箭头符号。Automaton 是所有有趣的箭头类的一个实例,包括 Loop 和 Circuit,因此您可以使用延迟来访问以前的值。(注意:再次,未经测试的代码)

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')

“延迟”箭头表示“上一个”等于“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

请注意“延迟”的输入如何包含“v”,这是一个从其输出派生的值。“rec”子句可以实现这一点,因此我们可以建立一个反馈循环。

于 2013-06-22T11:31:42.557 回答