Un autómata finito o PLC con un número finito de estados (en inglés autómata de estado finito o máquinas de estado finito o FSM ) es un modelo de cálculo matemático , utilizado en muchas circunstancias, desde el diseño de programas informáticos y recorridos lógicos secuenciales hasta aplicaciones en comunicación. protocolos , control de procesos , lingüística e incluso biología . Un autómata finito es una construcción matemática abstracta, capaz de estar en un número finito deestados , pero estando en un momento dado en un solo estado a la vez; el estado en el que se encuentra se denomina "estado actual". La transición de un estado a otro es activada por un evento o una condición; este pasaje se llama "transición". Un autómata particular se define por todos sus estados y todas sus transiciones.
Los autómatas finitos se encuentran comúnmente en muchos dispositivos que realizan acciones específicas en función de los eventos que ocurren. Un ejemplo es una máquina expendedora de bebidas que entrega el artículo deseado cuando la cantidad ingresada es apropiada. Otros ejemplos son los ascensores que saben combinar sucesivas llamadas para parar en plantas intermedias, semáforos que saben adaptarse a los coches que esperan, códigos digitales que analizan la correcta secuencia de cifras.
Los autómatas finitos pueden modelar una gran cantidad de problemas, incluido el diseño asistido por computadora para la electrónica , el diseño de protocolos de comunicación y el análisis sintáctico de idiomas. En la investigación de biología e inteligencia artificial , se han utilizado autómatas finitos o jerarquías de tales máquinas para describir sistemas neurológicos . En lingüística , se utilizan para describir las partes simples de las gramáticas de los lenguajes naturales . En la verificación de programas ( verificación de modelos ), se utilizan autómatas finitos, con a veces una gran cantidad de estados (miles de millones).
Visto como un modelo computacional, los autómatas finitos tienen un potencial bajo; tienen mucha menos potencia de cálculo que una máquina de Turing . En otras palabras, hay tareas que un autómata finito no puede realizar mientras que un autómata de empuje o una máquina de Turing sí. Esto se debe principalmente al hecho de que una máquina de estados tiene una memoria limitada a su número de estados.
El estudio de los autómatas finitos es una rama de la teoría de los autómatas .
Un ejemplo muy simple de un mecanismo que puede ser modelado por un autómata finito es una puerta de acceso . Una puerta, utilizada en algunos subterráneos u otros establecimientos de acceso controlado, es una puerta con tres brazos giratorios a la altura de la cintura. Al principio, los brazos están bloqueados y bloquean la entrada, e impiden que los usuarios pasen. La introducción de una moneda o ficha en una ranura de la puerta (o la presentación de un billete o una tarjeta) desbloquea los brazos y permite el paso de un solo usuario a la vez. Una vez que el usuario ha ingresado, los brazos se bloquean nuevamente hasta que se inserta una nueva ficha.
Una puerta, vista como una máquina de estados finitos, tiene dos estados: bloqueado ( " bloqueado " en inglés) y desbloqueado ( " desbloqueado " en inglés). Dos "entradas" pueden modificar el estado: la primera si inserta una ficha en la ranura (entrada de ficha ) y la segunda si empuja el brazo (entrada de empuje ). En el estado bloqueado, la acción de presionar no tiene ningún efecto: independientemente del número de veces que presione, el PLC permanece bloqueado. Si inserta una ficha, es decir, si haces un token de “entrada” , se pasa de la bloqueada estado a la desbloqueado estado . En el estado desbloqueado , agregar tokens adicionales no tiene ningún efecto y no cambia el estado. Pero tan pronto como un usuario gira el brazo de la puerta, proporcionando así un empujón , la máquina vuelve al estado bloqueado .
El autómata de una puerta se puede representar mediante una tabla de transición de estado que muestra, para cada estado, el nuevo estado y la salida (la acción) para una entrada determinada.
Estado actual | Entrada | Siguiente estado | Salida |
---|---|---|---|
Bloqueado | simbólico | desbloqueado | Desbloquee la puerta para que un usuario pueda pasar |
empujar | Bloqueado | Nada | |
desbloqueado | simbólico | desbloqueado | Nada |
empujar | Bloqueado | Cuando el usuario haya pasado, cierre la puerta. |
También podemos representar el autómata mediante un gráfico dirigido , llamado diagrama de transición de estado , como se indicó anteriormente. Cada estado está representado por un vértice (visualizado por un círculo). Los arcos (representados por flechas) muestran las transiciones de un estado a otro. Cada flecha tiene una entrada que activa la transición. Los datos que no provocan un cambio de estado, como un token para el estado desbloqueado , se representan mediante arcos circulares (bucles) que giran alrededor del estado. La flecha que ingresa al estado bloqueado desde el punto negro se usa para indicar que este estado es el estado inicial , al comienzo del modelado.
El siguiente ejemplo ilustra las posibilidades que se abren a un contrabandista que tiene que cruzar, de una orilla a otra, un lobo, una cabra y un repollo (es una variante de los muchos problemas de cruzar un río ). Su bote solo le permite llevar uno de los tres objetos a la vez y, por supuesto, no puede dejar el lobo y la cabra juntos, ni la cabra y el repollo. En el diagrama opuesto, un estado representa lo que el contrabandista ya ha podido transportar al otro lado ("P" representa al contrabandista, "L" al lobo, "C" a la cabra, y la col se ha señalado con "S "): al principio nada, al final todo. En las flechas, los objetos transportados (y él mismo). Una de las dos secuencias de transporte es CPLCSPC , la otra es CPSCLPC . Por supuesto, se descuidan los viajes de ida y vuelta innecesarios.
Un estado es la descripción de la configuración de un sistema en espera de realizar una transición. Una transición es un conjunto de acciones que se realizarán cuando se cumpla una condición o cuando se reciba un evento. Por ejemplo, un sistema de audio puede estar en un estado de "radio" y, cuando recibe un estímulo como " siguiente ", cambia a la siguiente estación de radio. Si el sistema está en el estado "CD" y recibe el estímulo " siguiente ", salta a la siguiente pista del CD actual. Por lo tanto, los mismos estímulos pueden desencadenar diferentes acciones, si el estado actual no es el mismo.
En algunas representaciones de máquinas finitas, es posible asociar acciones con un estado:
Se utilizan varios tipos de tablas de transición de estado . Estos diagramas son muy populares en UML en particular. La representación más común se muestra a continuación; la combinación del estado actual (por ejemplo, B ) y una entrada (por ejemplo, Y ) muestra el siguiente estado (en el ejemplo C ). La información completa asociada con una acción no se describe en la tabla y se puede agregar mediante anotaciones. Es posible definir una acción de máquina finita mediante tablas de transición en el modelo más desarrollado de autómata finito virtual (in) .
Entrada Expresar | Entrada X | Entrada Y | Entrada Z |
---|---|---|---|
Estado A | ... | ... | ... |
Estado B | ... | Estado C | ... |
Estado C | ... | ... | ... |
El lenguaje de especificación del Lenguaje de modelado unificado (UML) tiene su propia notación para describir los autómatas. Se trata de diagramas de comportamiento particulares que permiten superar las limitaciones de las máquinas de acabado tradicionales conservando sus principales ventajas. Las máquinas o autómatas UML introducen las nuevas nociones de diagramas de estructura compuesta , estados jerárquicos y agregación , al tiempo que amplían la noción de acción . Las máquinas terminadas UML tienen las propiedades de las máquinas Mealy y Moore que se describen a continuación. Soportan acciones que dependen tanto del estado del sistema como del evento desencadenante, como en las máquinas Mealy, y también acciones de entrada y salida asociadas con estados, como en las máquinas de Moore.
El lenguaje de especificación y descripción denominado lenguaje de especificación y descripción o SDL es un estándar desarrollado por la Unión Internacional de Telecomunicaciones (UIT). El estándar contiene un conjunto de símbolos gráficos que se utilizan para describir las acciones en una transición:
Un SDL contiene tipos básicos, pero principalmente tipos de datos abstractos (TDA) y una sintaxis de manipulación que permite que el sistema se describa formalmente, posiblemente de forma completa y sin ambigüedades.
Hay muchas variaciones de los diagramas de diagrama de estados, como el diagrama de un autómata de dos estados que se muestra arriba.
Los PLC son sistemas reactivos (in) , que responden a los pulsos recibidos. Desempeñan un papel importante en muchos campos diferentes, incluida la ingeniería eléctrica , la lingüística , la informática , la filosofía , la biología , las matemáticas y la lógica . Los autómatas finitos constituyen una clase de autómatas estudiados en la teoría de autómatas y la informática teórica .
En informática, los autómatas finitos se utilizan ampliamente en el modelado del comportamiento de las aplicaciones, en el diseño de hardware, en la electrónica digital , en la ingeniería de software , en la compilación , en los protocolos de comunicación , en el estudio de modelos computacionales y lenguajes formales . Los diccionarios lingüísticos también se pueden representar mediante un autómata finito. El ahorro de espacio para un diccionario de Scrabble en inglés puede alcanzar el 80%, e incluso más para los diccionarios de crucigramas en francés.
Los autómatas finitos se pueden clasificar principalmente en dos categorías, aceptores y transductores . Los aceptadores analizan la estructura de los datos proporcionados y la aceptan si se ajusta a la especificación descrita por el autómata. Los transductores, por el contrario, traducen una cadena de símbolos en otra, de nuevo según el algoritmo codificado en el autómata. En algunos casos, podemos encontrar variantes llamadas clasificadores y secuenciadores .
Los aceptadores , también conocidos como reconocedores, producen una salida binaria que indica si la entrada recibida es aceptada o no. Cada estado de dicho autómata es un estado de aceptación, también llamado final o terminal , o un estado de rechazo . Si el estado actual, después de leer toda la entrada, es un estado de aceptación, la entrada se acepta, de lo contrario, se rechaza. La entrada suele ser una serie de símbolos (letras); no hay acciones asociadas. El ejemplo de la figura 4 muestra un autómata finito que acepta la palabra "agradable". En este PLC, solo se acepta el estado 7.
Una máquina también puede describirse como la definición de un lenguaje formal. Este lenguaje se compone de palabras aceptadas por la máquina y ninguna palabra rechazada por ella. Por definición, los lenguajes aceptados por un autómata finito se denominan lenguajes reconocibles. Según el teorema de Kleene , estos son lenguajes regulares o racionales, descritos por expresiones regulares o racionales .
El problema de determinar el lenguaje aceptado por un autómata finito dado es un ejemplo de un problema más general llamado " problema de trayectoria algebraica " , que en sí mismo es una extensión de los problemas de desplazamiento en gráficas cuyos arcos llevan pesos tomados en una mitad arbitraria . anillo .
Estado inicialEl estado inicial generalmente se indica dibujando una flecha que apunta a ese estado "desde cualquier lugar".
Estados de aceptación, final o terminalUn estado de aceptación (también llamado estado de aceptación , final o terminal ) es un estado en el que la máquina declara que la cadena de entrada procesada hasta ahora pertenece al idioma que reconoce. Gráficamente, los estados de aceptación se representan con frecuencia mediante círculos duplicados. Otra forma, simétrica a la adoptada para el estado inicial, consiste en sacar una flecha “apuntando a ninguna parte” de dicho estado.
El estado inicial también puede ser un estado final; en este caso, el controlador acepta la cadena vacía. Si el estado inicial no es un estado de aceptación, y si no hay arco hacia un estado final, el autómata no acepta ninguna palabra.
La figura 5 es el ejemplo de un autómata finito determinista. Este autómata acepta secuencias binarias que incluyen un número par de dígitos 0. El estado S 1 es tanto el estado inicial como el estado terminal. El autómata termina en el estado S 1 si la cadena de lectura contiene un número par (posiblemente cero) de 0: cada 0 cambia de un estado a otro, mientras que un 1 deja el estado sin cambios. Ejemplos de cadenas aceptadas son ε , la palabra vacía , luego 1, 11, 11…, 00, 010, 1010, 10110, etc.
Los transductores finitos generan palabras en la salida en función de una palabra de entrada dada y de las acciones asociadas con los estados. Se utilizan, por ejemplo, en aplicaciones de control y en el campo de la lingüística computacional . Hay dos tipos de transductores, las máquinas de Moore y las máquinas de Mealy. Se diferencian en las modalidades que determinan los productos. Podemos demostrar que tienen el mismo poder de expresión.
Máquina de moore En el modelo de Moore, que solo usa acciones de entrada, la salida depende solo del estado actual. Comparado con el modelo de Mealy, el modelo de Moore tiene la ventaja de ser simple y fácil de entender. Considere, por ejemplo, una puerta de ascensor, modelada por una máquina que reconoce dos comandos: "abrir" y "cerrar", comandos que puede dar un usuario. La acción de entrada (E :) en el estado "en proceso de apertura" pone en marcha un motor que abre la puerta, y en el estado "en proceso de cierre" pone en marcha un motor que cierra la puerta. Los estados "abierto" y "cerrado" detienen el motor cuando la puerta está completamente abierta o completamente cerrada. También señalan esta situación al exterior mediante "puerta abierta" o "puerta cerrada". Máquina harinosa En el modelo de Mealy, que también utiliza acciones de entrada, la salida depende tanto de la entrada como del estado. El uso de máquinas Mealy a menudo reduce el número de estados. Por otro lado, el funcionamiento de un autómata es más complejo y más difícil de entender. La Figura 7 muestra un autómata de Mealy que tiene el mismo comportamiento que el autómata de Moore. Hay dos acciones de entrada (I :): "arrancar el motor para cerrar la puerta cuando llega el mando de cierre", y el mando simétrico de apertura. Los estados intermedios “en proceso de apertura” y “en proceso de cierre” no son necesarios.Las siguientes variantes son de uso bastante raro. Un clasificador es similar a un aceptador, pero tiene al menos dos estados terminales. Por tanto, un autómata de este tipo puede aceptar varios lenguajes simultáneamente, según la categoría de estados a los que pertenezca el estado terminal alcanzado al final de la lectura. Un secuenciador o generador es un caso especial de un autómata, que opera con un alfabeto de entrada de una sola letra. Tal autómata produce una secuencia única que puede interpretarse como el resultado de un transductor o un clasificador.
Un autómata finito con un solo estado a veces se llama "combinatorio"; solo usa acciones de entrada. Esta noción se puede utilizar cuando se supone que varios autómatas finitos trabajan juntos, comunicándose; Entonces puede ser conveniente considerar los autómatas combinatorios como un ladrillo en una herramienta de diseño.
Una distinción adicional importante es la que existe entre autómatas finitos deterministas y no deterministas . En un autómata determinista, cada estado tiene como máximo una transición para cada símbolo de entrada (e incluso exactamente una si el autómata está completo). En un autómata no determinista, un símbolo de entrada puede etiquetar una, más o ninguna transición para un estado dado. Esta distinción es importante en la práctica, pero menos en teoría porque existe un algoritmo (la construcción por subconjuntos ) que permite transformar un autómata finito no determinista en un autómata finito determinista con la misma funcionalidad. Sin embargo, y este es un sesgo que puede obstaculizar la eficiencia, el algoritmo de construcción de subconjuntos puede producir un autómata cuyo tamaño es exponencial con respecto al tamaño del autómata inicial. Es por eso que algunos algoritmos (como el programa grep de Unix) intentan comprometerse.
Hay otras formas de representar las máquinas de estado. Por ejemplo, existen herramientas para modelar y diseñar la lógica de los controladores integrados. Combinan estados jerárquicos de UML , diagramas de flujo de control y tablas de verdad en un solo lenguaje, lo que da un formalismo diferente y un conjunto específico de semántica. Estos diagramas son similares a las representaciones introducidas inicialmente por David Harel; soportan estados jerárquicamente anidados, regiones ortogonales en el sentido de UML , acciones sobre estados y transiciones.
Las definiciones formales son las siguientes:
Un autómata finito determinista se compone de:
Para los autómatas deterministas o no deterministas, es común considerar el caso donde es una función parcial , por lo tanto donde no está definido para ninguna combinación de un estado y un símbolo . Si no está configurado, el controlador informa un error y la entrada es rechazada. Esta variante es útil en la especificación de una máquina, pero algunos algoritmos que requieren que las funciones sean totales, requieren una transformación preliminar que, mediante la adición de un estado adicional, hace que la función de transición sea total.
Un autómata finito es una máquina de Turing muy particular, donde la cabeza solo puede realizar operaciones de lectura (y no escribir) y, además, siempre se mueve de izquierda a derecha (y por lo tanto no puede volver atrás).
Un transductor terminado se compone de:
Si la función de salida es una función de los estados y de la entrada ( ) la definición corresponde a la del modelo de Mealy ; si por el contrario la función de salida depende únicamente del estado, ( ), estamos en presencia del modelo de Moore .
No es difícil transformar un autómata de Moore en un autómata de Mealy haciendo que la función de salida dependa únicamente del estado de llegada. La conversión recíproca, de un autómata de Mealy a un autómata de Moore, también es posible, pero requiere la introducción de estados adicionales.
La optimización de un autómata finito significa aquí la búsqueda de un autómata finito determinista con el menor número de estados realizando la misma función. El algoritmo más rápido es el algoritmo de Hopcroft que data de 1971. Otras técnicas son el algoritmo de Moore y un algoritmo de Brzozowski . Los autómatas finitos acíclicos, que reconocen conjuntos finitos de palabras como diccionarios, pueden minimizarse en tiempo lineal. Se han realizado estudios extensos para comparar el promedio, el peor de los casos y la complejidad genérica de estos métodos. Optimizar un autómata en el sentido de encontrar un autómata finito determinista o no determinista con un número mínimo de estados es más complejo.
En electrónica digital , una máquina de estado se puede construir como un circuito lógico programable o un controlador programable industrial , con funciones lógicas realizadas por flip-flops o relés . Una implementación de hardware normalmente requiere un registro para almacenar variables de estado, un circuito lógico combinacional que determina las transiciones de estado y un segundo bloque lógico combinacional que determina las salidas del controlador. Una implementación común es el controlador Richards (en) .
Un caso especial de los autómatas de Moore, donde la salida está directamente conectada a los estados, se conoce como autómata de Medvedev. También se recomienda, en el diseño de chips, no colocar un circuito lógico entre la E / S primaria y los registros, para minimizar los retrasos entre chips que suelen ser largos y ralentizar la frecuencia de los PLC. También podemos optimizar los controladores para minimizar el consumo de energía mediante técnicas específicas (fr) .
Los siguientes conceptos se utilizan con frecuencia en la construcción de aplicaciones que utilizan autómatas finitos:
Los autómatas finitos se utilizan a menudo al comienzo del proceso de compilación en compiladores de lenguajes de programación. Dicha entidad puede incluir varios autómatas finitos, que implementan análisis léxico .
A partir de una secuencia de caracteres, un analizador léxico construye una secuencia de lexemas, como palabras reservadas, identificadores, literales; a partir de esta secuencia, el analizador de sintaxis construye el árbol de sintaxis. El analizador léxico y el parser manejan la parte regular y algebraica de la gramática de un lenguaje de programación.