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.

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *