Autómata finito en Haskell

Question

¿Cuál es una buena forma de representar al autómata finito en Haskell? ¿Cómo se vería el tipo de datos?

En nuestra universidad, los autómatas se definieron como una 5-tupla

(Q, X, delta, q_0, F) 

donde Q es el conjunto de estados del autómata, X es el alfabeto (es esta parte, incluso necessery), delta es la toma función de transición 2-tuple de (Q, X) y estado de retorno/-s (en versión no determinista) y F es el conjunto de estados de aceptación/final.

que es más importante, no estoy seguro de qué tipo delta debería tener ...

Answer 1

Hay dos opciones básicas:

• una función explícita delta :: Q -> X -> Q (o [Q] según el caso) como sugiere Sven Hager .
• Un mapa delta :: Map (Q, X) Q p. Ej. usando Data.Map, o si sus estados/alfabeto pueden ser indexados por los números ascendentes Data.Array o Data.Vector.

Tenga en cuenta que estos dos enfoques son esencialmente equivalentes, se puede convertir de la versión de mapa para una versión de función (esto es ligeramente diferente debido a un extra Maybe de la llamada lookup) con relativa facilidad

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

(o la versión adecuada al curry de la función de consulta para cualquier tipo de proyección que se están utilizando.)

---

Si usted está construyendo el auto mata en tiempo de compilación (y así conocer los posibles estados y puede tenerlos codificados como un tipo de datos), luego usar la versión de función le da mejor seguridad de tipo, ya que el compilador puede verificar que ha cubierto todos los casos.

Si usted está construyendo los autómatas en tiempo de ejecución (por ejemplo, desde la entrada del usuario), a continuación, almacenar delta como un mapa (y, posiblemente, hacer la conversión función que el anterior) y que tiene una verificación de entrada apropiada que garantice la corrección de manera que fromJust es segura (es decir, siempre hay una entrada en el mapa para cualquier posible tupla (Q,X), por lo que la búsqueda nunca falla (nunca devuelve Nothing)).

no determinista trabajo autómatas bien con la opción de mapa, porque un fracaso de búsqueda es lo mismo que tener ningún estado para ir a, es decir, una lista vacía [Q], y por lo que no tiene que ser cualquier manejo especial de Maybe más allá de una llamada a join . maybeToList (join es de Data.Monad y maybeToList es de Data.Maybe).

---

En una nota diferente, el alfabeto es definitivamente necesario: es cómo el autómata recibe la entrada.

Answer 2

Consulte el módulo Control.Arrow.Transformer.Automaton en el paquete "arrows".El tipo se ve así

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

Esto es un poco confuso porque es un transformador de flecha. En el caso más simple, puede escribir

type Auto = Automaton (->) 

Que usa funciones como la flecha subyacente. Sustituyendo (->) para "a" en la definición y Autómatas usando la notación infija se puede ver que esto es más o menos equivalente a:

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

En otras palabras, un autómata es una función que toma una entrada y devuelve un resultado y un nuevo autómata

Puede usar esto directamente escribiendo una función para cada estado que toma un argumento y devuelve el resultado y la siguiente función. Por ejemplo, aquí hay una máquina de estados para reconocer la expresión regular "a + b" (es decir, una serie de al menos una 'a' seguida de una 'b'). (Nota: el código no probado)

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) 

En cuanto a su pregunta original, Q = {estado1, estado2}, X = Char, delta es la aplicación de funciones, y F es la transición de estado volviendo True (en lugar de tener una "estado de aceptación" He utilizado una transición de salida con un valor de aceptación).

También puede utilizar la notación de Flecha. Automaton es una instancia de todas las clases de flechas interesantes, incluidos Loop y Circuit, por lo que puede obtener acceso a los valores anteriores mediante el uso de la demora. (Nota: una vez más, el código no probado)

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 flecha "retraso" significa que "prev" es igual al valor anterior de "c" en lugar del valor actual. También puede obtener acceso a su salida anterior mediante el uso de "rec". Por ejemplo, aquí hay una flecha que le da un total en descomposición a lo largo del tiempo. (En realidad probado en este 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 cómo la entrada a "retraso" incluye "v", un valor derivado de su salida. La cláusula "rec" lo habilita para que podamos crear un ciclo de retroalimentación.