pattern - restricciones multiples haskell

Autómata finito en Haskell

Question

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

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

(Q, X, delta, q_0, F)

donde Q es el conjunto de estados de autómatas, X es el alfabeto (si esta parte es necesaria), delta es la función de transición que toma 2-tuplas de (Q, X) y el estado de retorno / -s (en versión no determinista) y F es el conjunto de estados de aceptación / finalización.

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

Answer 1

Hay dos opciones básicas:

• Una función explícita delta :: Q -> X -> Q (o [Q] según corresponda) como sugiere Sven Hager.
• Un mapa delta :: Map (Q, X) Q por ejemplo, utilizando Data.Map , o si sus estados / alfabeto se pueden indexar con números ascendentes Data.Array o Data.Vector .

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

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

(O la versión con el currículum apropiado de la función de búsqueda para cualquier tipo de mapeo que esté usando).

Si está construyendo los autómatas en tiempo de compilación (y así conoce los posibles estados y puede codificarlos como un tipo de datos), el uso de la versión de la función le brinda una mejor seguridad de tipos, ya que el compilador puede verificar que ha cubierto todos los casos.

Si está construyendo los autómatas en tiempo de ejecución (por ejemplo, a partir de la entrada del usuario), entonces almacene delta como un mapa (y posiblemente realice la conversión de la función como se fromJust anteriormente) y tenga una validación de entrada adecuada que garantice la corrección para que desde fromJust sea ​​seguro (es decir, hay siempre una entrada en el mapa para cualquier tupla posible (Q,X) y, por lo tanto, la búsqueda nunca falla (nunca devuelve Nothing )).

Los autómatas no deterministas funcionan bien con la opción de mapa, porque una búsqueda fallida es lo mismo que no tener un estado al que ir, es decir, una lista [Q] vacía, por lo que no es necesario que haya un manejo especial de la Maybe más allá de una llamada para join . maybeToList 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

Verifique el módulo Control.Arrow.Transformer.Automaton en el paquete de "flechas". 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 sencillo puedes escribir.

type Auto = Automaton (->)

Que utiliza funciones como la flecha subyacente. Sustituir (->) por "a" en la definición de autómata y al usar la notación infijo, puede ver que esto es aproximadamente 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: 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 términos de su pregunta original, Q = {estado1, estado2}, X = Char, delta es la aplicación de función, y F es la transición de estado que devuelve Verdadero (en lugar de tener un "estado de aceptación", he usado una transición de salida con una aceptando valor).

Alternativamente, puede utilizar la notación de flecha. Automaton es una instancia de todas las clases de flecha interesantes, incluyendo Loop y Circuito, para que pueda obtener acceso a los valores anteriores utilizando el retardo. (Nota: de nuevo, 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 de "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 usando "rec". Por ejemplo, aquí hay una flecha que le da un total en descomposición con el tiempo. (Realmente 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

Observe cómo la entrada a "retraso" incluye "v", un valor derivado de su salida. La cláusula "rec" lo habilita, por lo que podemos crear un bucle de retroalimentación.