Haskell中的有限自动机

Question

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

在我们学院,自动机被定义为5元组

(Q, X, delta, q_0, F)

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

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

Answer 1

有两个基本选项:

• Sven Hager建议的显式函数delta :: Q -> X -> Q(或[Q]适当的).
• 地图,delta :: Map (Q, X) Q例如使用Data.Map,或者您的州/字母可以通过升序编号Data.Array或索引Data.Vector.

请注意,这两种方法基本上是等效的,可以相对容易地将地图版本转换为函数版本(由于Maybe来自lookup调用的额外内容而略有不同)

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

(或者您正在使用的任何映射类型的查找函数的适当curry版本.)

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

如果您在运行时构建自动机(例如,从用户输入),然后存储delta为地图(并且可能执行上述功能转换)并具有适当的输入验证,以确保正确性以确保fromJust安全(即始终存在在地图中输入任何可能的(Q,X)元组,因此查找永远不会失败(永不返回Nothing)).

非确定性自动机与map选项配合良好,因为失败的查找与没有状态可以进行相同,即空[Q]列表,因此不需要对调用之外的任何特殊处理Maybe到join . maybeToList(join来自Data.Monad和maybeToList来自Data.Maybe).

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

Answer 2

Check out the Control.Arrow.Transformer.Automaton module in the "arrows" package. The type looks like this

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

This is a bit confusing because its an arrow transformer. In the simplest case you can write

type Auto = Automaton (->)

Which uses functions as the underlying arrow. Substituting (->) for "a" in the Automaton definition and using infix notation you can see this is roughly equivalent to:

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

In other words an automaton is a function that takes an input and returns a result and a new automaton.

You can use this directly by writing a function for each state that takes an argument and returns the result and the next function. For instance, here is a state machine to recognise the regexp "a+b" (that is, a series of at least one 'a' followed by a 'b'). (Note: untested code)

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)

In terms of your original question, Q = {state1, state2}, X = Char, delta is function application, and F is the state transition returning True (rather than having an "accepting state" I've used an output transition with an accepting value).

Alternatively you can use Arrow notation. Automaton is an instance of all the interesting arrow classes, including Loop and Circuit, so you can get access to previous values by using delay. (Note: again, untested code)

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

The "delay" arrow means that "prev" is equal to the previous value of "c" rather than the current value. You can also get access to your previous output by using "rec". For instance, here is an arrow that gives you a decaying total over time. (Actually tested in this case)

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

Note how the input to "delay" includes "v", a value derived from its output. The "rec" clause enables this, so we can build up a feedback loop.