Teoría de los autómatas

Clases de automata

(Haga clic en cada capa obtiene un artículo sobre ese tema)

El autómata descrito por este diagrama de estado comienza en estado S₁, y los cambios estados siguiendo las flechas marcadas 0 o 1 según los símbolos de entrada cuando llegan. El doble círculo marca S₁ como estado de aceptación. Desde todos los caminos de S₁ para sí mismo contener un número uniforme de flechas marcadas 0, este autómata acepta cadenas que contienen incluso números de 0s.

Teoría de autómatas es el estudio de máquinas abstractas y autómatas, así como de los problemas computacionales que pueden resolverse con ellos. Es una teoría en informática teórica. La palabra autómata proviene de la palabra griega αὐτόματος, que significa "autoactuación, voluntad propia, movimiento propio". Un autómata (autómata en plural) es un dispositivo informático abstracto autopropulsado que sigue una secuencia predeterminada de operaciones automáticamente. Un autómata con un número finito de estados se denomina autómata finito (FA) o máquina de estado finito (FSM). La figura de la derecha ilustra una máquina de estados finitos, que es un tipo de autómata bien conocido. Este autómata consta de estados (representados en la figura por círculos) y transiciones (representadas por flechas). Cuando el autómata ve un símbolo de entrada, hace una transición (o salto) a otro estado, de acuerdo con su función de transición, que toma como argumentos el estado anterior y el símbolo de entrada actual.

La teoría de los autómatas está estrechamente relacionada con la teoría del lenguaje formal. En este contexto, los autómatas se utilizan como representaciones finitas de lenguajes formales que pueden ser infinitos. Los autómatas a menudo se clasifican por la clase de lenguajes formales que pueden reconocer, como en la jerarquía de Chomsky, que describe una relación de anidamiento entre las principales clases de autómatas. Los autómatas juegan un papel importante en la teoría de la computación, la construcción de compiladores, la inteligencia artificial, el análisis y la verificación formal.

Historia

La teoría de los autómatas abstractos se desarrolló a mediados del siglo XX en relación con los autómatas finitos. La teoría de autómatas se consideró inicialmente como una rama de la teoría de sistemas matemáticos, que estudiaba el comportamiento de los sistemas de parámetros discretos. Los primeros trabajos en la teoría de los autómatas diferían de los trabajos anteriores sobre sistemas al utilizar el álgebra abstracta para describir los sistemas de información en lugar del cálculo diferencial para describir los sistemas materiales. La teoría del transductor de estado finito fue desarrollada bajo diferentes nombres por diferentes comunidades de investigación. El concepto anterior de máquina de Turing también se incluyó en la disciplina junto con nuevas formas de autómatas de estado infinito, como los autómatas pushdown.

1956 vio la publicación de Automata Studies, que recopiló el trabajo de científicos como Claude Shannon, W. Ross Ashby, John von Neumann, Marvin Minsky, Edward F. Moore y Stephen Cole Kleene. Con la publicación de este volumen, "la teoría de los autómatas emergió como una disciplina relativamente autónoma". El libro incluía la descripción de Kleene del conjunto de eventos regulares, o lenguajes regulares, y una medida relativamente estable de complejidad en los programas de la máquina de Turing de Shannon. En el mismo año, Noam Chomsky describió la jerarquía de Chomsky, una correspondencia entre autómatas y gramáticas formales, y Ross Ashby publicó Una introducción a la cibernética, un libro de texto accesible que explica los autómatas y la información utilizando la teoría básica de conjuntos.

El estudio de los autómatas acotados lineales condujo al teorema de Myhill-Nerode, que proporciona una condición necesaria y suficiente para que un lenguaje formal sea regular y un recuento exacto del número de estados en una máquina mínima para el lenguaje. El lema de bombeo para lenguajes regulares, también útil en pruebas de regularidad, fue probado en este período por Michael O. Rabin y Dana Scott, junto con la equivalencia computacional de autómatas finitos deterministas y no deterministas.

En la década de 1960, un cuerpo de resultados algebraicos conocido como "teoría de la estructura" o "teoría de la descomposición algebraica" surgió, que se ocupaba de la realización de máquinas secuenciales a partir de máquinas más pequeñas por interconexión. Si bien cualquier autómata finito se puede simular utilizando un conjunto de puertas universales, esto requiere que el circuito de simulación contenga bucles de complejidad arbitraria. La teoría de la estructura se ocupa del "bucle libre" realizabilidad de las máquinas. La teoría de la complejidad computacional también tomó forma en la década de 1960. A finales de la década, la teoría de los autómatas pasó a ser vista como "las matemáticas puras de la informática".

Autómatas

Lo que sigue es una definición general de un autómata, que restringe una definición más amplia de un sistema a uno que actúa en pasos de tiempo discretos, con su comportamiento de estado y salidas definidas en cada paso por funciones inmutables de solo su estado y aporte.

Descripción informal

Un autómata se ejecuta cuando se le da alguna secuencia de entradas en pasos de tiempo discretos (individuales) (o simplemente pasos). Un autómata procesa una entrada seleccionada de un conjunto de símbolos o letras, que se denomina alfabeto de entrada. Los símbolos recibidos por el autómata como entrada en cualquier paso son una secuencia de símbolos llamados palabras. Un autómata tiene un conjunto de estados. En cada momento durante la ejecución del autómata, el autómata está en uno de sus estados. Cuando el autómata recibe una nueva entrada, pasa a otro estado (o transiciones) en función de una función de transición que toma el estado anterior y el símbolo de entrada actual como parámetros. Al mismo tiempo, otra función llamada función de salida produce símbolos del alfabeto de salida, también de acuerdo con el estado anterior y el símbolo de entrada actual. El autómata lee los símbolos de la palabra de entrada y realiza transiciones entre estados hasta que la palabra se lee por completo, si tiene una longitud finita, momento en el que el autómata se detiene. Un estado en el que el autómata se detiene se denomina estado final.

Para investigar las posibles secuencias de estado/entrada/salida en un autómata utilizando la teoría del lenguaje formal, se puede asignar a una máquina un estado de inicio y un conjunto de estados de aceptación. Luego, dependiendo de si una ejecución que comienza desde el estado inicial termina en un estado de aceptación, se puede decir que el autómata acepta o rechaza una secuencia de entrada. El conjunto de todas las palabras aceptadas por un autómata se denomina lenguaje reconocido por el autómata. Un ejemplo familiar de una máquina que reconoce un idioma es una cerradura electrónica, que acepta o rechaza los intentos de ingresar el código correcto.

Definición formal

Automaton

Un autómata puede ser representado formalmente por un 5-tuple M=.. .. ,.. ,Q,δ δ ,λ λ .. {displaystyle M=langle SigmaGammaQ,deltalambda rangle }, donde:

• .. {displaystyle Sigma } es un conjunto finito de símbolos, llamado el entrada del autómata,
• .. {displaystyle "Gamma" es otro conjunto finito de símbolos, llamado el alfabeto del autómata,
• Q{displaystyle Q} es un conjunto de estados,
• δ δ {displaystyle delta } es función siguiente al estado o función de transición δ δ :Q× × .. → → Q{displaystyle delta: Qtimes Sigma to Q} mapeando pares de entradas estatales a estados sucesores,
• λ λ {displaystyle lambda } es función de próxima salida λ λ :Q× × .. → → .. {displaystyle lambda: Qtimes Sigma to Gamma } mapear pares de entrada de estado a salidas.

Si Q{displaystyle Q} es finito, entonces M{displaystyle M} es un autómata finito.

Palabra de entrada

Un autómata lee una cadena finita de símbolos a1a2...an{displaystyle a_{1}a_{2}a_{n}, donde ai▪ ▪ .. {displaystyle a_{i}in Sigma }, que se llama palabra de entrada. El conjunto de todas las palabras es denotado por .. Alternativa Alternativa {displaystyle Sigma ^{*}.

Corre

Una secuencia de estados q0,q1,...,qn{displaystyle q_{0},q_{1},, donde qi▪ ▪ Q{displaystyle q_{i}in Q} tales que qi=δ δ ()qi− − 1,ai){displaystyle q_{i}=delta (q_{i-1},a_{i})} para <math alttext="{displaystyle 00.i≤ ≤ n{displaystyle 0 madeileq n}<img alt="{displaystyle 0, es un Corre del autómata en una entrada a1a2...an▪ ▪ .. Alternativa Alternativa {displaystyle a_{1}a_{2}a_{n}in Sigma ^{*} desde el estado q0{displaystyle q_{0}. En otras palabras, al principio el autómata está en el estado inicial q0{displaystyle q_{0}, y recibe entrada a1{displaystyle A_{1}. Para a1{displaystyle A_{1} y todos los siguientes ai{displaystyle A_{i} en la cuerda de entrada, el autómata elige el siguiente estado qi{displaystyle q_{i} según la función de transición δ δ ()qi− − 1,ai){displaystyle delta (q_{i-1},a_{i})}, hasta el último símbolo an{displaystyle a_{n} ha sido leído, dejando la máquina en estado final de la carrera, qn{displaystyle q_{n}. Del mismo modo, en cada paso, el autómata emite un símbolo de salida según la función de salida λ λ ()qi− − 1,ai){displaystyle lambda (q_{i-1},a_{i})}.

Función de transición δ δ {displaystyle delta } se amplía inductivamente δ δ ̄ ̄ :Q× × .. Alternativa Alternativa → → Q{displaystyle {fnMicrosoft {fnMicrosoft} }:Qtimes Sigma ^{*}to Q} para describir el comportamiento de la máquina cuando se alimentan palabras enteras de entrada. Para la cuerda vacía ε ε {displaystyle varepsilon }, δ δ ̄ ̄ ()q,ε ε )=q{displaystyle {overline {delta}(q,varepsilon)=q} para todos los estados q{displaystyle q}, y para cuerdas wa{displaystyle wa} Donde a{displaystyle a} es el último símbolo y w{displaystyle w} es el (posiblemente vacío) resto de la cuerda, δ δ ̄ ̄ ()q,wa)=δ δ ()δ δ ̄ ̄ ()q,w),a){displaystyle {deline {delta}(q,wa)=delta ({overline {delta }(q,w),a)}. La función de salida λ λ {displaystyle lambda } puede ampliarse de forma similar λ λ ̄ ̄ ()q,w){fnMicrosoft Sans Serif}, que da la salida completa de la máquina cuando se ejecuta en la palabra w{displaystyle w} del estado q{displaystyle q}.

Aceptador

Para estudiar un autómata con la teoría de las lenguas formales, un autómata puede considerarse como un autómata aceptante, reemplazando el alfabeto de salida y la función .. {displaystyle "Gamma" y λ λ {displaystyle lambda } con

• q0▪ ▪ Q{displaystyle q_{0}in Q}, un designado start state, y
• F{displaystyle F}, un conjunto de estados de Q{displaystyle Q} (i.e. F⊆ ⊆ Q{displaystyle Fsubseteq Q}Se llama aceptar estados.

Esto permite definir lo siguiente:

Aceptar palabra

Una palabra w=a1a2...an▪ ▪ .. Alternativa Alternativa {displaystyle... Sigma ^{*} es un aceptar palabra para el autómata si δ δ ̄ ̄ ()q0,w)▪ ▪ F{displaystyle {overline {delta}(q_{0},w)in F}, es decir, si después de consumir toda la cuerda w{displaystyle w} la máquina está en un estado de aceptación.

Idioma reconocido

El idioma L⊆ ⊆ .. Alternativa Alternativa {displaystyle Lsubseteq Sigma ^{*} reconocida por un autómata es el conjunto de todas las palabras que son aceptadas por el autómata, L={}w▪ ▪ .. Alternativa Alternativa Silencioδ δ ̄ ̄ ()q0,w)▪ ▪ F}{displaystyle L=win Sigma ^{*}\fn {deline {delta}(q_{0},w)in F}.

Idiomas reconocibles

Los idiomas reconocibles son el conjunto de idiomas que algunos autómatas reconocen. Para automata finita los idiomas reconocibles son idiomas regulares. Para diferentes tipos de automata, los idiomas reconocibles son diferentes.

Definiciones variantes de autómatas

Los autómatas se definen para estudiar máquinas útiles bajo formalismo matemático. Entonces, la definición de un autómata está abierta a variaciones de acuerdo con la "máquina del mundo real" que queremos modelar usando el autómata. La gente ha estudiado muchas variaciones de autómatas. Las siguientes son algunas variaciones populares en la definición de diferentes componentes de autómatas.

Input

• Entrada finita: Un autómata que acepta sólo secuencias finitas de símbolos. La definición introductoria anterior sólo abarca palabras finitas.
• Infinita entrada: Un autómata que acepta palabras infinitas (Clásico-palabras). Tal automata se llama ω-automata.
• Entrada de árbol: La entrada puede ser una árbol de símbolos en lugar de secuencia de símbolos. En este caso después de leer cada símbolo, el autómata lecturas todos los símbolos sucesores en el árbol de entrada. Se dice que el autómata hace una copia de sí mismo para cada sucesor y cada copia comienza a correr en uno de los símbolos sucesores del estado según la relación de transición del autómata. Tal autómata se llama autómata de árboles.
• Infinito árbol de entrada: Las dos extensiones anteriores se pueden combinar, por lo que el autómata lee una estructura de árboles con (en) ramas definitivas. Tal autómata se llama autómata de árboles infinitos.

Estados

• Estado único: Un autómata con un estado, también llamado circuito combinado, realiza una transformación que puede implementar la lógica combinada.
• Estados finitos: Un autómata que contiene sólo un número finito de estados.
• Estados Infinitos: Un autómata que puede no tener un número finito de estados, o incluso un número contable de estados. Se pueden utilizar diferentes tipos de memoria abstracta para dar tales máquinas descripciones finitas.
• Memoria apilada: Un autómata también puede contener un poco de memoria adicional en la forma de una pila en la que los símbolos pueden ser empujados y picados. Este tipo de autómata se llama automatizado.
• Memoria de búsqueda: Un autómata puede tener memoria en forma de cola. Tal máquina se llama máquina de cola y es Turing-complete.
• Memoria de cinta: Las entradas y salidas de la automata se describen a menudo como entrada y salida cintas. Algunas máquinas tienen más cintas de trabajo, incluyendo la máquina Turing, autómata ligada lineal y transductor log-space.

Función de transición

• Deterministic: Para un estado actual dado y un símbolo de entrada, si un autómata sólo puede saltar a uno y sólo un estado entonces es un autómata determinista.
• Nondeterministic: Un autómata que, después de leer un símbolo de entrada, puede saltar a cualquiera de varios estados, como está autorizado por su relación de transición. Observe que la función de transición de término es reemplazada por relación de transición: El autómata no determinista decide saltar en una de las opciones permitidas. Tal automata se llama automata no determinante.
• Suplementación: Esta idea es bastante similar a la automata del árbol pero ortogonal. El autómata puede funcionar múltiples copias sobre igual Siguiente símbolo de lectura. Tal automata se llama automata alternante. La condición de aceptación debe estar satisfecha en todos los ámbitos de tales copias para aceptar la entrada.

Condiciones de aceptación

• Aceptación de palabras finitas: Lo mismo que se describe en la definición informal anterior.
• Aceptación de palabras infinitas: un ω-automaton no puede tener estados finales, como palabras infinitas nunca terminan. Más bien, la aceptación de la palabra se decide mirando la secuencia infinita de los estados visitados durante la carrera.
• Aceptación probabilística: Un autómata no necesita aceptar o rechazar estrictamente una entrada. Puede aceptar la entrada con cierta probabilidad entre cero y uno. Por ejemplo, la automata finita cuántica, la automata geométrica y la automata métrica tienen aceptación probabilística.

Diferentes combinaciones de las variaciones anteriores producen muchas clases de autómatas.

La teoría de los autómatas es un tema que estudia las propiedades de varios tipos de autómatas. Por ejemplo, se estudian las siguientes preguntas sobre un tipo dado de autómatas.

• ¿Qué clase de idiomas formales es reconocible por algún tipo de automata? (Idiomas reconocibles)
• Son ciertas automatas cerrado bajo unión, intersección o complementación de idiomas formales? (Propiedades de seguridad)
• ¿Qué expresivo es un tipo de automata en términos de reconocer una clase de idiomas formales? ¿Y su poder expresivo relativo? (Jorra de idiomas)

La teoría de autómatas también estudia la existencia o inexistencia de algoritmos efectivos para resolver problemas similares a la siguiente lista:

• ¿Un autómata acepta al menos una palabra de entrada? (Comprobación del empleo)
• ¿Es posible transformar un autómata no-determinista dado en un autómata determinista sin cambiar el idioma reconocido? (Determinación)
• Para un lenguaje formal dado, ¿cuál es el autómata más pequeño que lo reconoce? (Minimización)

Tipos de autómatas

La siguiente es una lista incompleta de tipos de autómatas.

Autómatas discretos, continuos e híbridos

Normalmente, la teoría de los autómatas describe los estados de las máquinas abstractas, pero existen autómatas discretos, autómatas analógicos o autómatas continuos, o autómatas híbridos discretos-continuos, que utilizan datos digitales, datos analógicos o tiempo continuo, o y datos analógicos, respectivamente.

Jerarquía en términos de poderes

La siguiente es una jerarquía incompleta en términos de potencias de diferentes tipos de máquinas virtuales. La jerarquía refleja las categorías anidadas de lenguajes que las máquinas pueden aceptar.

Aplicaciones

Cada modelo en la teoría de autómatas juega un papel importante en varias áreas aplicadas. Los autómatas finitos se utilizan en el procesamiento de texto, compiladores y diseño de hardware. La gramática libre de contexto (CFG) se utiliza en lenguajes de programación e inteligencia artificial. Originalmente, los CFG se utilizaron en el estudio de los lenguajes humanos. Los autómatas celulares se utilizan en el campo de la vida artificial, siendo el ejemplo más famoso el Juego de la vida de John Conway. Algunos otros ejemplos que podrían explicarse utilizando la teoría de autómatas en biología incluyen patrones de pigmentación y crecimiento de moluscos y piñas. Yendo más allá, algunos científicos defienden una teoría que sugiere que todo el universo es computado por algún tipo de autómata discreto. La idea se originó en el trabajo de Konrad Zuse y fue popularizada en Estados Unidos por Edward Fredkin. Los autómatas también aparecen en la teoría de campos finitos: el conjunto de polinomios irreducibles que se pueden escribir como composición de polinomios de grado dos es de hecho un lenguaje regular. Otro problema para el que se pueden utilizar los autómatas es la inducción de lenguajes regulares.

Simuladores de autómatas

Los simuladores de autómatas son herramientas pedagógicas que se utilizan para enseñar, aprender e investigar la teoría de los autómatas. Un simulador de autómatas toma como entrada la descripción de un autómata y luego simula su funcionamiento para una cadena de entrada arbitraria. La descripción del autómata se puede introducir de varias formas. Un autómata se puede definir en un lenguaje simbólico o se puede ingresar su especificación en un formulario prediseñado o se puede dibujar su diagrama de transición haciendo clic y arrastrando el mouse. Los simuladores de autómatas más conocidos incluyen Turing's World, JFLAP, VAS, TAGS y SimStudio.

Conexión con la teoría de categorías

Se pueden definir varias categorías distintas de autómatas siguiendo la clasificación de autómatas en diferentes tipos descrita en la sección anterior. La categoría matemática de autómatas deterministas, máquinas secuenciales o autómatas secuenciales, y máquinas de Turing con homomorfismos de autómatas que definen las flechas entre autómatas es una categoría cartesiana cerrada, tiene tanto límites categóricos como colímites. Un homomorfismo de autómatas mapea un quíntuple de un autómata A_i en el quíntuple de otro autómata A_j. Los homomorfismos de autómatas también se pueden considerar como transformaciones de autómatas o como homomorfismos de semigrupos, cuando el espacio de estado, S, del autómata se define como un semigrupo S_g. Los monoides también se consideran una configuración adecuada para autómatas en categorías monoidales.

Categorías de automata variable

Uno también podría definir un variable autómata, en el sentido de Norbert Wiener en su libro sobre El uso humano de los seres humanos via los endomorfismos Ai→ → Ai{displaystyle A_{i}to A_{i}. Entonces se puede demostrar que tales homomorfismos automáticos variables forman un grupo matemático. En el caso de automata no determinista u otros tipos complejos, este último conjunto de endomorfismos puede convertirse, sin embargo, en un variable grupo autómata. Por lo tanto, en el caso más general, las categorías de automata variable de cualquier tipo son categorías de grupoides o categorías de grupoides. Además, la categoría de automata reversible es entonces una 2-categoría, y también una subcategoría de la 2-categoría de grupoides, o la categoría de grupoides.