Domanda Automa finito in Haskell


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

Nel nostro college, gli automi sono stati definiti come una tupla da 5

(Q, X, delta, q_0, F)

dove Q è l'insieme degli stati dell'automa, X è l'alfabeto (è anche questa parte necessaria), delta è la funzione di transizione che prende 2-tuple da (Q, X) e restituisce stato / -s (in versione non deterministica) e F è l'insieme di stati di accettazione / fine.

Soprattutto, non sono sicuro di quale tipo delta avrebbe dovuto...


20
2018-06-16 13:47


origine


risposte:


Ci sono due opzioni di base:

  • Una funzione esplicita delta :: Q -> X -> Q (o [Q] come appropriato) come suggerisce Sven Hager.
  • Una cartina delta :: Map (Q, X) Q per esempio. utilizzando Data.Map, o se i tuoi stati / alfabeto possono essere indicizzati con numeri crescenti Data.Array o Data.Vector.

Si noti che questi due approcci sono essenzialmente equivalenti, uno può convertire dalla versione di mappa a una versione di funzione (questo è leggermente diverso a causa di un extra Maybe dal lookup chiamata) relativamente facilmente

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

(Oppure la versione appropriatamente curata della funzione di ricerca per qualunque tipo di mappatura stai usando).


Se stai costruendo gli automi in fase di compilazione (e quindi conosci gli stati possibili e li puoi codificare come un tipo di dati), allora la versione della funzione ti offre una sicurezza migliore, poiché il compilatore può verificare di aver coperto tutti i casi.

Se stai costruendo gli automi in fase di esecuzione (ad es. Da input dell'utente), quindi memorizzandoli delta come una mappa (e possibilmente facendo la conversione di funzione come sopra) e avendo una validazione di input appropriata che garantisce la correttezza in modo che fromJust è sicuro (cioè c'è sempre una voce nella mappa per ogni possibile (Q,X) tupla e così la ricerca non fallisce mai (non ritorna mai Nothing)).

Gli automi non deterministici funzionano bene con l'opzione mappa, perché una ricerca fallita è la stessa di non avere uno stato in cui andare, cioè un vuoto [Q] lista, e quindi non c'è bisogno di essere qualunque trattamento speciale del Maybe oltre una chiamata a join . maybeToList (join è da Data.Monad e maybeToList è da Data.Maybe).


Su una nota diversa, l'alfabeto è assolutamente necessario: è il modo in cui l'automa riceve input.


17
2018-06-16 14:29



Controlla il modulo Control.Arrow.Transformer.Automaton nel pacchetto "frecce". Il tipo sembra così

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

Quale funzione funge da freccia sottostante. Sostituendo (->) per "a" nella definizione di Automaton e usando la notazione infisso si può vedere che è approssimativamente 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 della domanda originale, Q = {state1, state2}, X = char, delta è l'applicazione di funzione, e F è la transizione di stato che restituisce True (piuttosto che avere uno "stato di accettazione" ho usato una transizione di output con un accettando valore).

In alternativa puoi usare la notazione Arrow. 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: di nuovo, 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 "delay" significa che "prev" è uguale al valore precedente di "c" piuttosto che al 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. (Effettivamente testato 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

Nota come l'input di "delay" include "v", un valore derivato dal suo output. La clausola "rec" abilita questo, quindi possiamo creare un ciclo di feedback.


12
2018-06-22 11:31