Automa finito in Haskell

Question

Qual è un buon modo per rappresentare l'automa finito in Haskell? Come sarebbe il tipo di dati di esso?

Nel nostro collegio, automi sono stati definiti come un 5-pla

(Q, X, delta, q_0, F) 

dove Q è l'insieme degli stati dell'automa, X è l'alfabeto (è questa parte anche necessery), Delta è la funzione di transizione presa 2-tuple from (Q, X) e return state/-s (in versione non deterministica) e F è l'insieme degli stati di accettazione/fine.

cosa più importante, non sono sicuro di che tipo delta dovrebbe avere ...

Answer 1

Ci sono due opzioni di base:

• una funzione esplicita delta :: Q -> X -> Q (o [Q] a seconda dei casi) come suggerisce Sven Hager .
• Una mappa delta :: Map (Q, X) Q ad es. utilizzando Data.Map o se i tuoi stati/alfabeto possono essere indicizzati dai numeri ascendenti Data.Array o Data.Vector.

Si noti che questi due approcci sono sostanzialmente equivalenti, si può convertire dalla versione della mappa per una versione di funzione (questo è leggermente diverso a causa di un extra Maybe dalla chiamata lookup) in modo relativamente facile

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

(o la versione in modo appropriato al curry della funzione look-up per qualsiasi tipo di mappatura che si utilizza.)

---

Se si sta costruendo l'auto mata in fase di compilazione (e quindi conoscere i possibili stati e possono averli codificati come un tipo di dati), quindi utilizzare la versione della funzione ti dà una migliore sicurezza di tipo, in quanto il compilatore può verificare che hai coperto tutti i casi.

Se state costruendo l'automi in fase di esecuzione (ad esempio da input dell'utente), quindi memorizzare delta come mappa (e possibilmente facendo la conversione funzione come sopra) e presentante una validazione ingresso appropriato che garantisce la correttezza modo che fromJust è sicuro (cioè c'è sempre una voce nella mappa per ogni possibile tupla (Q,X) e quindi la ricerca non fallisce mai (non restituisce mai Nothing)).

non deterministico lavoro automi bene con l'opzione di carta, perché un look-up fallito è lo stesso che avere nessuno stato di andare in, vale a dire un [Q] lista vuota, e quindi non non ha bisogno di essere qualsiasi gestione speciale di Maybe oltre una chiamata a join . maybeToList (join è da Data.Monad e maybeToList è da Data.Maybe).

---

Su una nota diversa, l'alfabeto è sicuramente necessaria: è come l'automa riceve l'input.

Answer 2

Controllare il modulo Control.Arrow.Transformer.Automaton nel pacchetto "frecce".Il tipo assomiglia a questo

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

Questo è un po 'di confusione perché è un trasformatore di frecce. Nel caso più semplice puoi scrivere

type Auto = Automaton (->) 

Quali usi funziona come la freccia sottostante. Sostituendo (->) per "a" nella definizione Automa e l'utilizzo di notazione infissa potete vedere questo è più o meno equivalente a:

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

In altre parole un automa è una funzione che prende un input e restituisce un risultato e un nuovo automa.

È possibile utilizzarlo direttamente scrivendo una funzione per ogni stato che accetta un argomento e restituisce il risultato e la funzione successiva. Ad esempio, ecco una macchina a stati per riconoscere la regexp "a + b" (cioè una serie di almeno una "a" seguita da una "b"). (Nota: codice non testato)

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 termini di domanda originale, Q = {stato1, Stato2}, X = Char, Delta è l'applicazione funzione e F è il passaggio dello stato di ritorno True (piuttosto che avere un "accepting state" Ho usato una transizione di output con un valore accettabile).

In alternativa è possibile utilizzare la notazione a freccia. Automaton è un'istanza di tutte le classi di frecce interessanti, tra cui Loop e Circuito, in modo da poter accedere ai valori precedenti utilizzando il ritardo. (Nota: nuovamente, codice non testato)

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

La freccia "ritardo" che "prev" è uguale al valore precedente di "c" anziché il valore corrente. Puoi anche accedere al tuo output precedente usando "rec". Ad esempio, ecco una freccia che ti dà un totale in decomposizione nel tempo. (In realtà testata in questo caso)

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

Si noti come l'ingresso di "ritardo" comprende "v", un valore derivato dalla sua uscita. La clausola "rec" abilita questo, quindi possiamo creare un ciclo di feedback.