Teoría de la computación: máquinas de estados finitos

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 la máquina de estados finitos

Máquinas de estado finito se componen de estos componentes:

• Conjunto de conocidos Estados: 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:

• Estado inicial: el punto de partida de nuestro sistema. Los estados iniciales generalmente se dibujan con una flecha apuntando hacia ellos:

• Conjunto de Estados Aceptantes: 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:

• Alfabeto: también denominado 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. Por lo general, se dibujan como dos estados conectados por una línea:

Demostración del analizador binario

Creemos una máquina de estados finitos que analiza 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:

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, pasamos 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 estado finito 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 dado de estados y transiciones:

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

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

los FSM clase, después de ser inicializada, necesita el add_transitions() método a llamar. Este método valida que nuestras reglas de transición estén configuradas con estados válidos.

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

Probémoslo con el analizador binario que creamos anteriormente. Siga el código, ejecútelo y tome nota de los resultados:

# 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 estado finito se utilizan 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 estado finito. Veamos cada componente central e identifiquemos qué sería para los semáforos:

• Estados: un semáforo tiene generalmente tres estados: rojo, verde y amarillo.
• Estado inicial: Verde
• Estados Aceptantes: 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:

IA enemiga

Finite State Machines nos permite mapear el flujo de acciones en los jugadores controlados por computadora de un juego. Digamos que estábamos 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 shooter simplista podemos tener: Patrulla, Atacar, Recargar, Ponerse a cubierto y Fallecido.
• Estado inicial: Como es un guardia, el estado inicial sería Patrulla.
• Estados Aceptantes: Un robot enemigo ya no puede aceptar entradas cuando está muerto, por lo que nuestro estado Fallecido será el nuestro.
• Alfabeto: Para simplificar, podemos usar constantes de cadena para representar un estado mundial: enfoques del jugador, carreras del jugador, 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:
  • Patrulla
    • Si un jugador se acerca, pasa al estado de Ataque.
    • Si nos quedamos sin salud, pasamos al estado Fallecido.
  • Ataque
    • Si la munición es baja, vaya al estado de recarga.
    • Si la salud es baja, vaya al estado Ponerse a cubierto.
    • Si el jugador escapa, ve al estado de Patrulla.
    • Si nos quedamos sin salud, pasamos al estado Fallecido.
  • Recargar
    • Si la munición está llena, ve al estado de ataque.
    • Si la salud es baja, vaya al estado Ponerse a cubierto.
    • Si nos quedamos sin salud, pasamos al estado Fallecido.
  • Ponerse a cubierto
    • Si la salud está llena, ve al estado de ataque.
    • Si la munición es baja, vaya al estado de recarga.
    • Si nos quedamos sin salud, pasamos al estado Fallecido.

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

Limitaciones

El principal beneficio de las máquinas de estado finito, 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 unos seguidos del mismo número de ceros, no podemos crear una máquina de estados finitos para ella. Una máquina de estados finitos no realiza un seguimiento del número 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 expresiones regulares, con las que puede estar familiarizado por los lenguajes de programación, sino más bien una clasificación de idiomas entonces no se puede construir una máquina de estados finitos para ello. Puede obtener más información sobre esta prueba y sus implicaciones. Aquí.

Conclusión

Las máquinas de estados finitos son un marco teórico que podemos utilizar 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 una secuencia de entradas sería aceptada.

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 Pumping Lemma. Aun así, las máquinas de estado finito tienen muchas aplicaciones del mundo real y son populares por su simplicidad.