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

Introducción

Una máquina de estados finitos es un modelo de cálculo, 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 se componen de estos componentes:
  • Conjunto de estados conocidos : como su nombre lo indica, debe haber una cantidad finita de estados en los que puede estar nuestro sistema. Solo un estado puede estar activo a la vez. Los estados suelen ser dibujados con círculos:
Estado
  • Estado inicial : el punto de partida de nuestro sistema. Los estados iniciales generalmente se dibujan con una flecha que se les señala:
Estado inicial
  • 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 se dibujan generalmente como un círculo doble:
Aceptando estado
  • 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. Estos usualmente se dibujan como dos estados conectados por una línea:
Transición

Demostración de analizador binario

Vamos a crear una máquina de estados finitos que analice una secuencia binaria donde cada vez que encontremos un 1, inmediatamente encontremos 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:
Analizador binario
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, nos movemos 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, vamos 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 lo mantiene allí, ya que no puede hacer una transición fuera del estado de error.

Creando un FSM en Python

Muchas soluciones de software implementan Finite State Machines para gestionar algunos aspectos 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
La Transitionclase contiene una match()función. Una forma rápida para que sepamos si el estado actual y la entrada de la máquina de estados finitos nos permitirán pasar al siguiente estado definido.
La FSMclase, después de ser inicializada, necesita el add_transitions()método para ser llamado. Este método valida que nuestras reglas de transición estén configuradas con estados válidos.
Luego 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.
Vamos a probarlo con el analizador binario que creamos anteriormente. Sigue el código, ejecútalo y toma 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 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 simple sistema de semáforo se puede modelar con una máquina de estados finitos. Veamos cada componente central e identifiquemos lo que 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 se ejecutan de forma indefinida, por lo que no habría estados de aceptación para este modelo.
  • Alfabeto : enteros positivos que representan segundos.
  • transiciones :
    • Si estamos en estado verde y esperamos 360 segundos (6 minutos), podemos pasar al estado amarillo.
    • Si estamos en el estado Amarillo y esperamos 10 segundos, entonces podemos ir al estado Rojo.
    • Si estamos en estado rojo y esperamos 120 segundos, entonces podemos ir al estado verde.
Esta máquina de estados finitos se puede dibujar de la siguiente manera:
Semáforos máquina de estado finito

Enemigo enemigo

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 tirador simplista podemos tener: Patrulla, Ataque, Recargar, Cubrir y Fallecido.
  • Estado inicial : Como es un guardia, el estado inicial sería Patrulla.
  • Estados aceptores : un robot enemigo ya no puede aceptar comentarios cuando está muerto, por lo que nuestro estado fallecido será nuestro que lo acepte.
  • Alfabeto : para simplificar, podemos usar constantes de cadena para representar un estado mundial: enfoques de jugador, carreras de jugador, salud total, salud baja, falta de 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, ve al estado de ataque.
      • Si nos quedamos sin salud, ve al estado fallecido.
    • Ataque
      • Si la munición es baja, vaya al estado de carga.
      • Si la salud es baja, vaya al estado Take Cover.
      • Si el jugador se escapa, vaya al estado de Patrulla.
      • Si nos quedamos sin salud, ve al estado fallecido.
    • Recargar
      • Si la munición está llena, ve al estado de ataque.
      • Si la salud es baja, vaya al estado Take Cover.
      • Si nos quedamos sin salud, ve 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 carga.
      • Si nos quedamos sin salud, ve al estado fallecido.
Esta máquina de estados finitos se puede dibujar de la siguiente manera:
Guardia AI

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 1s seguido del mismo número de 0s, no podemos crear una Máquina de Estados Finitos para ella. 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 está comprobado por el Lema de bombeo, una prueba que afirma que si un lenguaje no es regular (no tanto las expresiones regulares, con las que puede estar familiarizado con los lenguajes de programación, sino una clasificación de lenguajes , no se puede construir una máquina de estados finitos). 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 usar para modelar sistemas. Dado un conjunto conocido de estados, el estado de inicio, 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í, Finite State Machines tiene muchas aplicaciones en el mundo real y son populares debido a su simplicidad.

Acerca de: Programator

Somos Instinto Programador

0 comentarios:

Publicar un comentario

Dejanos tu comentario para seguir mejorando!

Con tecnología de Blogger.