2012-06-16 21 views
20

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

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

+3

Nel caso di un automa deterministico, Delta potrebbe essere del tipo Q -> X -> Q Nel caso di un automa non deterministico, avrei scelto qualcosa come Q -> X -> [Q] –

+0

Cosa Sven Hager dice, e 'F' potrebbe essere implementato come' isEnd :: Q -> Bool' –

risposta

17

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.

+0

ThanQ per una risposta completa e completa :-) Solo un'altra domanda: quando si converte l'espressione regolare in automa, cosa è meglio modo di rappresentare delta? Devo implementare operazioni come _concatenation_, _disjunction_ e _iteration_ di automi. Mi sembra che la mappa sia il vincitore o mi sbaglio? – mathemage

+0

@mathemage, puoi provare a implementare entrambi e vedere quale ti piace (proverei prima la versione della mappa). Inoltre, se questa risposta ti è stata utile, devi votarla e, se risponde alla tua domanda, puoi indicarla come accettato con il segno di spunta: [il faq ha qualche dettaglio in più] (http://stackoverflow.com/faq#howtoask). – huon

+0

@mathemage: Se usi la freccia Automaton (vedi la mia risposta completa qui sotto), allora penso che tu possa esprimere quelle operazioni in termini di funzioni combinatorie. Ad esempio la disgiunzione sarebbe una funzione che passa l'input ai suoi due stati di argomento e restituisce una nuova funzione che è la disgiunzione dei due risultati. –

12

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.