Teoría de la Computación: Máquinas de Estados Finitos

Una máquina de estados finitos es un modelo de computación, es decir, una herramienta conceptual para diseñar sistemas. Procesa una secuencia de entradas que cambia el estado del sistema...

Introducción

Una máquina de estados finitos es un modelo de computación, es decir, una herramienta conceptual para diseñar sistemas. Procesa una secuencia de entradas que cambia el estado del sistema.

Cuando se procesa toda la entrada, observamos el estado final del sistema para determinar si la secuencia de entrada fue aceptada o no.

Componentes de máquina de estado finito

[Las máquinas de estados finitos] (https://en.wikipedia.org/wiki/Finite-state_machine) se componen de los siguientes componentes:

  • Conjunto de estados conocidos: como su nombre lo indica, debe haber una cantidad finita de estados en los que nuestro sistema puede estar. Solo un estado puede estar activo a la vez. Los estados generalmente se dibujan con círculos:

State

  • Estado Inicial: el punto de partida de nuestro sistema. Los estados iniciales generalmente se dibujan con una flecha que los señala:

Initial State

  • Conjunto de Estados de aceptación: un subconjunto de estados conocidos que indica si la entrada que procesamos es válida o no. Los estados de aceptación generalmente se dibujan como un círculo doble:

Accepting State

  • Alfabeto: también conocido como Idioma, es el conjunto de todas las entradas válidas.
  • Transiciones: reglas que dictan cómo la máquina se mueve de un estado a otro. Estos generalmente se dibujan como dos estados conectados por una línea:

Transition

Demostración de analizador binario

Vamos a crear una máquina de estados finitos que analice una secuencia binaria donde cada vez que encontramos un 1, inmediatamente encontramos un 0. Por ejemplo, 1010 es una secuencia de entrada válida, pero 1110 y 1010100 no lo son.

Podemos crear una máquina de estados finitos como esta:

Binary Parser

Nuestra Máquina de Estados Finitos tiene 3 estados: Estado 1, Estado 2 y Error.

Aquí, tenemos algunas situaciones posibles:

  • Si estamos en el Estado 1 y encontramos un 1, pasamos al Estado 2.
  • Si estamos en el Estado 2 y encontramos un 0, volvemos al Estado 1.
  • Si estamos en el Estado 1 y encontramos un 0, pasamos al estado de Error.
  • Si estamos en el Estado 2 y encontramos un 1, vamos al estado de Error.

Como observará, cualquier entrada en el estado de error la mantiene allí, ya que no puede salir del estado de error.

Creando un FSM en Python

Muchas soluciones de software implementan máquinas de estados finitos para administrar algún aspecto de los estados. Podemos implementar una máquina de estados finitos en Python y verificar mediante programación la entrada para un conjunto determinado de estados y transiciones:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Transition:
    """A change from one state to a next"""

    def __init__(self, current_state, state_input, next_state):
        self.current_state = current_state
        self.state_input = state_input
        self.next_state = next_state

    def match(self, current_state, state_input):
        """Determines if the state and the input satisfies this transition relation"""
        return self.current_state == current_state and self.state_input == state_input

class FSM:
    """A basic model of computation"""

    def __init__(
            self,
            states=[],
            alphabet=[],
            accepting_states=[],
            initial_state=''):
        self.states = states
        self.alphabet = alphabet
        self.accepting_states = accepting_states
        self.initial_state = initial_state
        self.valid_transitions = False

    def add_transitions(self, transitions=[]):
        """Before we use a list of transitions, verify they only apply to our states"""
        for transition in transitions:
            if transition.current_state not in self.states:
                print(
                    'Invalid transition. {} is not a valid state'.format(
                        transition.current_state))
                return
            if transition.next_state not in self.states:
                print('Invalid transition. {} is not a valid state'.format)
                return
        self.transitions = transitions
        self.valid_transitions = True

    def __accept(self, current_state, state_input):
        """Looks to see if the input for the given state matches a transition rule"""
        # If the input is valid in our alphabet
        if state_input in self.alphabet:
            for rule in self.transitions:
                if rule.match(current_state, state_input):
                    return rule.next_state
            print('No transition for state and input')
            return None
        return None

    def accepts(self, sequence):
        """Process an input stream to determine if the FSM will accept it"""
        # Check if we have transitions
        if not self.valid_transitions:
            print('Cannot process sequence without valid transitions')

        print('Starting at {}'.format(self.initial_state))
        # When an empty sequence provided, we simply check if the initial state
        # is an accepted one
        if len(sequence) == 0:
            return self.initial_state in self.accepting_states

        # Let's process the initial state
        current_state = self.__accept(self.initial_state, sequence[0])
        if current_state is None:
            return False

        # Continue with the rest of the sequence
        for state_input in sequence[1:]:
            print('Current state is {}'.format(current_state))
            current_state = self.__accept(current_state, state_input)
            if current_state is None:
                return False

        print('Ending state is {}'.format(current_state))
        # Check if the state we've transitioned to is an accepting state
        return current_state in self.accepting_states

La clase Transition contiene una función match(). Una forma rápida de saber si el estado actual y la entrada de la máquina de estados finitos nos permitirán pasar al siguiente estado definido.

La clase FSM, después de inicializarse, necesita que se llame al método add_transitions(). Este método valida que nuestras reglas de transición estén configuradas con estados válidos.

Luego podemos usar el método accepts() con una lista de entradas para determinar si nuestra máquina estaría en un estado de aceptación.

Vamos a probarlo con el analizador binario que creamos anteriormente. Siga el código, ejecútelo y tome nota de los resultados:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# Set up our FSM with the required info:
# Set of states
states = ['State 1', 'State 2', 'Error']
# Set of allowed inputs
alphabet = [1, 0]
# Set of accepted states
accepting_states = ['State 1']
# The initial state
initial_state = 'State 1'
fsm = FSM(states, alphabet, accepting_states, initial_state)

# Create the set of transitions
transition1 = Transition('State 1', 1, 'State 2')
transition2 = Transition('State 2', 0, 'State 1')
transition3 = Transition('State 1', 0, 'Error')
transition4 = Transition('State 2', 1, 'Error')
transition5 = Transition('Error', 1, 'Error')
transition6 = Transition('Error', 0, 'Error')
transitions = [
    transition1,
    transition2,
    transition3,
    transition4,
    transition5,
    transition6]
# Verify and add them to the FSM
fsm.add_transitions(transitions)

# Now that our FSM is correctly set up, we can give it input to process
# Let's transition the FSM to a green light
should_be_accepted = fsm.accepts([1, 0, 1, 0])
print(should_be_accepted)

# Let's transition the FSM to a red light
should_be_rejected_1 = fsm.accepts([1, 1, 1, 0])
print(should_be_rejected_1)

# Let's transition to yellow and give it bad input
should_be_rejected_2 = fsm.accepts([1, 0, 1, 0, 1, 0, 0])
print(should_be_rejected_2)

Ejemplos

Las máquinas de estados finitos se usan comúnmente en sistemas del mundo real que se extienden más allá del análisis de cadenas e incluso más allá de los sistemas de software.

Semáforos

Un sistema de semáforo simple se puede modelar con una máquina de estados finitos. Veamos cada componente central e identifiquemos cuál sería para los semáforos:

  • Estados: un semáforo generalmente tiene tres estados: Rojo, Verde y Amarillo.
  • Estado inicial: Verde
  • Estados de aceptación: en el mundo real, los semáforos funcionan indefinidamente, por lo que no habría estados de aceptación para este modelo.
  • Alfabeto: números enteros positivos que representan segundos.
  • Transiciones:
  • Si estamos en el estado Verde y esperamos 360 segundos (6 minutos), podemos pasar al estado Amarillo.
  • Si estamos en el estado Amarillo y esperamos 10 segundos, podemos pasar al estado Rojo.
  • Si estamos en el estado Rojo y esperamos 120 segundos, podemos pasar al estado Verde.

Esta máquina de estados finitos se puede dibujar de la siguiente manera:

Traffic Lights Finite State Machine

IA enemiga

Finite State Machines nos permite mapear el flujo de acciones en los jugadores controlados por computadora de un juego. Digamos que estamos haciendo un juego de acción donde los guardias patrullan un área del mapa. Podemos tener una máquina de estados finitos con las siguientes propiedades:

  • Estados: Para nuestro tirador simplista podemos tener: Patrullar, Atacar, Recargar, Cubrirse y Fallecido.
  • Estado Inicial: Como es un guardia, el estado inicial sería Patrulla.
  • Estados de aceptación: un bot enemigo ya no puede aceptar entradas cuando está muerto, por lo que nuestro estado Fallecido será nuestro estado de aceptación.
  • Alfabeto: para simplificar, podemos usar constantes de cadena para representar un estado mundial: El jugador se acerca, el jugador corre, Salud completa, Salud baja, Sin salud, Munición completa y Munición baja.
  • Transiciones: como este modelo es un poco más complejo que los semáforos, podemos separar las transiciones examinando un estado a la vez:
    • Patrol
      • If a player approaches, go to the Attack state.
      • If we run out of health, go to the Deceased state.
    • Attack
      • If ammo is low, go to the Reload state.
      • If health is low, go to the Take Cover state.
      • If the player escapes, go to the Patrol state.
      • If we run out of health, go to the Deceased state.
    • Reload
      • If ammo is full, go to the Attack state.
      • If health is low, go to the Take Cover state.
      • If we run out of health, go to the Deceased state.
    • Take Cover
      • If health is full, go to the Attack state.
      • If ammo is low, go to the Reload state.
      • If we run out of health, go to the Deceased state.

Esta máquina de estados finitos se puede dibujar de la siguiente manera:

Guard AI

Limitaciones

El principal beneficio de las máquinas de estados finitos, su simplicidad, también se convierte en una de sus desventajas. Los sistemas que necesitan una cantidad indeterminada de estados no pueden ser modelados por una Máquina de Estados Finitos, evidentemente.

Anteriormente modelamos una máquina de estados finitos que aceptaba la cadena '10' para cualquier cantidad de iteraciones. Si tuviéramos que aceptar una cadena de cualquier número de 1 seguidos por el * mismo número * de 0, no podemos crear una máquina de estados finitos para él. Una máquina de estados finitos no realiza un seguimiento de la cantidad de estados que visitó, solo es consciente del estado actual en el que se encuentra.

Esto lo demuestra el Pumping Lemma, una prueba que afirma que si un lenguaje no es regular (no tanto las expresiones regulares, con las que puede estar familiarizado por los lenguajes de programación, sino una clasificación de [idiomas] (https://en .wikipedia.org/wiki/Chomsky_hierarchy), entonces no se puede construir una máquina de estados finitos para él. Puede obtener más información sobre esta demostración y sus implicaciones [aquí](http://codeinjection.blogspot.com/2011/02/pumping- lema-y-por-que-es-un-ligero-mas.html).

Conclusión

Las máquinas de estados finitos son un marco teórico que podemos usar para modelar sistemas. Dado un conjunto conocido de estados, el estado inicial, el estado de aceptación y las reglas para la transición entre estados, podemos determinar si se aceptaría una secuencia de entradas.

La cantidad limitada de estados que se pueden modelar no hace que estas máquinas abstractas sean adecuadas para todos los sistemas, como lo muestra el lema de bombeo. Aun así, las máquinas de estados finitos tienen muchas aplicaciones en el mundo real y son populares debido a su simplicidad.

Licensed under CC BY-NC-SA 4.0