20

Haskellで有限オートマトンを表現する良い方法は何ですか？そのデータ型はどのようになりますか？

私たちの大学では、オートマトンは5タプルとして定義されていました

(Q, X, delta, q_0, F)

ここで、Qはオートマトンの状態のセット、Xはアルファベット（この部分は必要です）、deltaは（Q、X）から2タプルを取得し、状態/ -s（非決定論的バージョン）を返す遷移関数です。 Fは、受け入れ/終了状態のセットです。

最も重要なのは、どのタイプが必要かわからないことですdelta...

4

2 に答える 2

18

2つの基本的なオプションがあります。

  • Sven Hagerが示唆する明示的な関数delta :: Q -> X -> Q（または必要に応じて）。[Q]
  • delta :: Map (Q, X) Qたとえば、を使用しているマップ、または州/アルファベットを昇順の数字またはData.Mapでインデックス付けできる場合。Data.ArrayData.Vector

これらの2つのアプローチは本質的に同等であり、マップバージョンから関数バージョンに比較的簡単に変換できることに注意してください（これは呼び出しMaybeからの余分なもののためにわずかに異なります）lookup

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

（または、使用しているマッピングタイプに応じて、適切にカレーされたバージョンのルックアップ関数。）

コンパイル時にオートマトンを構築している場合（そして可能な状態を知っていて、それらをデータ型としてエンコードできる場合）、コンパイラーはすべてのケースをカバーしたことをコンパイラーが検証できるため、関数バージョンを使用すると型の安全性が向上します。

実行時にオートマトンを構築している場合（たとえば、ユーザー入力から）、deltaマップとして保存し（場合によっては上記のように関数変換を実行し）、安全であるように正確性を保証する適切な入力検証を行いfromJustます（つまり、常に可能な(Q,X)タプルのマップへのエントリであるため、ルックアップが失敗することはありません（戻ることはありませんNothing））。

非決定性オートマトンはマップオプションでうまく機能します。失敗したルックアップは、移動する状態がない、つまり空のリストと同じであり、呼び出し以外の特別な処理は[Q]必要ないためです。Maybe to join . maybeToList（joinからData.MonadでmaybeToListあり、からですData.Maybe）。

別の注意点として、アルファベットは間違いなく必要です。それは、オートマトンが入力を受け取る方法です。

于 2012-06-16T14:29:06.417 に答える
13

「arrows」パッケージの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"（つまり、一連の少なくとも1つの'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を含むすべての興味深い矢印クラスのインスタンスであるため、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')

「遅延」矢印は、「前」が現在の値ではなく「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」句はこれを可能にするので、フィードバックループを構築できます。

于 2013-06-22T11:31:42.557 に答える