Autómata finito

El origen de los autómatas finitos probablemente se remonta a su uso implícito en máquinas electromecánicas, desde principios del siglo XX.Si el estado final en el que se detuvo es un estado de aceptación, entonces la cadena pertenece al lenguaje reconocido por el autómata; en caso contrario, la cadena no pertenece a dicho lenguaje., permitiendo caracterizar los autómatas de manera más abreviada y sin perder expresividad.[6]​ La función δ* puede expresarse también de manera recursiva, definiendo para toda cadena x ∈ Σ*, todo símbolo a ∈ Σ, y un estado q ∈ Q:[6]​ Se llama configuración de un autómata finito a un "instante" en el cómputo de la máquina; es decir, al estado actual en que se encuentra dicho cómputo, junto con la palabra que ha sido procesada hasta ese momento.De este modo, se puede definir además la configuración inicial del autómata, como el par (q0,x), donde x es la entrada; y la configuración final, como el par (q,ε), con q ∈ F. De este modo, el lenguaje regular aceptado por un autómata finito A puede denotarse como L(A) = {w; δ*(q0,w)∈ F}, es decir, como el conjunto de todas las configuraciones iniciales que conllevan a estados finales.Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado q ∈ Q en que se encuentre el autómata, y con cualquier símbolo a ∈ Σ del alfabeto leído, existe siempre a lo más una transición posible δ(q,a).Un autómata finito no determinista (abreviado AFND) es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.Haciendo la analogía con los AFDs, en un AFND puede darse cualquiera de estos dos casos: Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε).Se dice que dos autómatas finitos son equivalentes, si ambos reconocen el mismo lenguaje regular.[9]​ Dada una expresión regular, es posible construir un AFND-ε que reconozca dicho lenguaje, por ejemplo mediante el algoritmo de Thompson.La conversión implica pasar por un AFD intermedio con estados y transiciones redundantes, que al no ser accesibles a partir del estado inicial, son eliminados para obtener el AFD definitivo.Para definir el AFD intermedio, se deben seguir los siguientes pasos: En las figuras de ejemplo, como el AFND inicial posee tres estados (q0, q1, q2), entonces el AFD intermedio poseerá siete ({q0}, {q1}, {q2}, {q0, q1}, {q0, q2}, {q1, q2}, {q0, q1, q2}), y como el estado final original era q2, entonces los estados finales del AFD intermedio son {q2}, {q0, q2}, {q1, q2} y {q0, q1, q2}.De hecho, existen algoritmos más eficientes aún que el mostrado en este artículo (aunque menos intuitivos).[11]​ Sin embargo, el problema de minimizar un autómata finito no determinista es NP-completo y PSPACE-completo.[12]​[13]​ En la primera figura del ejemplo, se muestra un autómata con el estado inaccesible d, el cual puede eliminarse inmediatamente.Posteriormente, se marcan las celdas restantes de acuerdo a la cuarta línea del algoritmo, notando que el par (b, f) queda asociado con el par (c, g), y así finalmente se obtiene el autómata final, agrupando los estados b y f, así como c y g, tal y como se muestra en la segunda figura del ejemplo.Existen diversas generalizaciones posibles de hacer sobre los autómatas finitos, para aumentar su uso y expresividad.