Finite Automat in Haskell

Question

Was ist eine gute Möglichkeit, endliche Automaten in Haskell darzustellen? Wie würde der Datentyp aussehen?

In unserem College, als 5-Tupel-Automaten wurden

(Q, X, delta, q_0, F) 

definiert, wobei Q die Gruppe der Automaten der Zustände ist, X das Alphabet (dieser Teil auch necessery) ist, Delta ist die Übergangsfunktion Mitnahmen 2-Tupel von (Q, X) und Rückkehrzustand/-s (in nicht-deterministischer Version) und F ist die Menge von akzeptierenden/Endzuständen.

Am wichtigsten ist, ich bin nicht sicher, welche Art delta sollte ...

Answer 1

Es gibt zwei grundlegende Optionen:

• Eine explizite Funktion delta :: Q -> X -> Q (oder [Q] entsprechend) als Sven Hager schlägt vor, .
• Eine Karte delta :: Map (Q, X) Q z.B. mit Data.Map, oder wenn Ihre Stati/Alphabet kann durch aufsteigende Zahlen Data.Array oder Data.Vector indiziert werden.

Beachten Sie, dass diese beiden Ansätze im Wesentlichen gleichwertig sind, kann man von der Karte Version auf eine Funktionsversion umwandeln (dies aufgrund einer zusätzlichen Maybe vom lookup Anruf etwas anders ist) relativ leicht

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

(Oder die entsprechend curried Version der Look-up-Funktion für was auch immer Mapping-Typ Sie verwenden.)

---

Wenn Sie das auto bauen Mata zur Kompilierzeit (und damit die möglichen Zustände kennen und sie als Datentyp codieren lassen), dann gibt Ihnen die Verwendung der Funktionsversion eine bessere Typsicherheit, da der Compiler überprüfen kann, ob Sie alle Fälle abgedeckt haben.

Wenn Sie die Automaten zur Laufzeit bauen (zB von Benutzereingaben), dann delta als eine Karte zu speichern (und möglicherweise die Funktion Umwandlung wie oben tun) und mit einer geeigneten Eingabevalidierung, die Richtigkeit garantiert, so dass fromJust sicher ist (dh es gibt immer einen Eintrag in der Map für jedes mögliche (Q,X) Tupel und so schlägt die Suche nie fehl (gibt nie Nothing zurück).

Nicht-deterministische Automaten arbeiten gut mit der Karte Option, weil ein ausgefallener Look-up die gleiche ist kein Zustand zu gehen, wie, dh eine leere [Q] Liste, und so ist es nicht sein müssen jede spezielle Handhabung der Maybe über einen Anruf hinaus zu join . maybeToList (join ist von Data.Monad und maybeToList ist von Data.Maybe).

Auf eine andere Anmerkung, das Alphabet ist auf jeden Fall notwendig: Es ist, wie der Automat die Eingabe erhält.

Answer 2

Überprüfen Sie das Modul Control.Arrow.Transformer.Automaton im Paket "arrows".Der Typ sieht so aus:

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

Dies ist ein bisschen verwirrend, weil es ein Pfeil Transformator ist. Im einfachsten Fall können Sie schreiben

type Auto = Automaton (->) 

Welche Funktionen als zugrunde liegenden Pfeil verwendet. Setzt man (->) für „a“ in der Automaton Definition und Infix-Notation können Sie sehen, dies entspricht in etwa:

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

Mit anderen Worten: ein Automat ist eine Funktion, die eine Eingabe nimmt und gibt ein Ergebnis zurück und ein neuer Automat.

Sie können dies direkt verwenden, indem Sie eine Funktion für jeden Zustand schreiben, der ein Argument akzeptiert und das Ergebnis und die nächste Funktion zurückgibt. Zum Beispiel ist hier eine Zustandsmaschine, um das Regexp "a + b" zu erkennen (dh eine Folge von mindestens einem "a", gefolgt von einem "b"). (Anmerkung: ungetestet 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 Bezug auf Ihre ursprüngliche Frage, Q = {state1, state2}, X = Char, Delta-Funktion Anwendung und F ist der Zustandsübergang Rückkehr True (eher als ein mit "accepting state" Ich habe einen Ausgabeübergang mit einem akzeptierenden Wert verwendet.

Alternativ können Sie die Pfeilnotation verwenden. Automaton ist eine Instanz aller interessanten Pfeilklassen, einschließlich Loop und Circuit, sodass Sie mithilfe von Delay auf vorherige Werte zugreifen können. (Anmerkung: wieder, ungetesteten 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') 

Der „Verzögerung“ bedeutet, dass Pfeil „prev“ gleich den vorherigen Wert von „c“ eher als der aktuellen Wert. Sie können mit "rec" auch auf Ihre vorherige Ausgabe zugreifen. Hier ist zum Beispiel ein Pfeil, der Ihnen im Laufe der Zeit eine verfallende Gesamtsumme gibt. (In diesem Fall tatsächlich getestet)

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

Hinweis, wie der Eingang auf „Verzögerung“ umfaßt „v“ einen Wert von seinem Ausgang abgeleitet. Der "rec" -Klausel ermöglicht dies, so dass wir eine Rückkopplungsschleife aufbauen können.