¿Qué tan práctica es la teoría de autómatas?

Siempre hay una forma de aplicación en temas relacionados con la informática teórica. Pero los libros de texto y los cursos de pregrado generalmente no explican la razón por la que la teoría de autómatas es un tema importante y si todavía tiene aplicaciones en la práctica. Por lo tanto, los estudiantes de pregrado podrían tener problemas para comprender la importancia de la teoría de autómatas y podrían pensar que ya no tiene ningún uso práctico.

¿La teoría de autómatas sigue siendo útil en la práctica?

¿Debería ser parte del plan de estudios de pregrado CS?

1. ¿Alguna vez usó una herramienta como grep / awk / sed? Las expresiones regulares forman el corazón de estas herramientas.

2. Se sorprenderá de la cantidad de codificación que puede evitar mediante el uso basado en principios de expresiones regulares, en "proyectos prácticos", como un servidor de correo electrónico.

3. Si eres un experto en CS, definitivamente estarás escribiendo un compilador / intérprete para un lenguaje (al menos pequeño). Si alguna vez ha intentado esta tarea antes y se ha quedado atascado, apreciará lo mucho que una pequeña teoría (también conocida como gramáticas libres de contexto) puede ayudarlo. Esta teoría ha convertido una tarea una vez imposible en algo que se puede completar durante un fin de semana. (Y le ganó al inventor un premio Turing - google BNF).

4. Si eres un experto en CS, en algún momento, debes sentarte y pensar en los fundamentos filosóficos de la informática, y no solo en lo genial que es la próxima versión de la API de Android. En una nota relacionada, el trabajo de la universidad no es prepararte para los próximos 5 años de tu vida, sino prepararte para los próximos 50. Lo único que pueden hacer a este respecto es ayudarte a pensar - pensar de la teoría de autómatas como uno de esos cursos.

Una de las manifestaciones más prácticas de CS es la construcción de compiladores. En 1965, Knuth comenzó el estudio de los analizadores LR. Rápidamente (en menos de una década), tuvimos analizadores LALR que son un subconjunto de autómatas deterministas de empuje que nos permiten implementar los analizadores shift / reduce.

En el corazón de la viabilidad y eficiencia del análisis LALR hay una prueba (por Knuth) de que los "prefijos" del lenguaje resultan ser regulares (su autómata finito). Esta es la génesis de los generadores de analizadores automáticos como yacc / bison, etc.

Es seguro decir que los lenguajes de programación tal como los conocemos deben gran parte de su eficiencia de compilación a estos desarrollos.

Aquí hay otro ejemplo: el corazón del protocolo TCP / IP es una máquina de estados finitos. ¿Cuánto más práctico puede ser?

Todo estudiante serio de CS, especialmente los prácticos, debe prestar atención a la teoría de autómatas. Es la base de gran parte de la riqueza de la informática.

¿Puedes escuchar ese ruido ? Es el sonido de miles de teoremas, aplicaciones y herramientas brillantes que se ríen en el cielo de los autómatas teóricos.

Los idiomas y los autómatas son conceptos elegantes y robustos que encontrará en todas las áreas de la informática. Las lenguas no son secas, las formalistas son parte de la prehistoria informática. La perspectiva de la teoría del lenguaje destila preguntas aparentemente complicadas sobre objetos sofisticados y opacos en declaraciones simples sobre palabras y árboles. Los lenguajes formales desempeñan un papel en la informática similar al punto de vista fundamental y cambiante que el álgebra y la topología aportan a las matemáticas clásicas. Aquí hay algunos problemas prácticos, bastante complicados y prácticos que se abordan a través de la teoría del lenguaje.

1. Desea detectar ocurrencias duplicadas de una frase en un documento y eliminar la segunda aparición. En esencia, desea sustituir una secuencia en un idioma.
2. ¿Un programa contiene una violación de afirmación? ¿Un controlador de dispositivo respeta ciertos protocolos cuando interactúa con el núcleo? El comportamiento de un programa es un conjunto de ejecuciones; en otras palabras, un idioma. La propiedad de corrección es otro idioma. El problema de corrección del programa equivale a una verificación de inclusión de idioma.
3. ¿Puede su software estar atascado en un bucle infinito? ¿Un algoritmo distribuido contiene un livelock? Necesitamos idiomas sobre palabras infinitas, pero la vista de inclusión de idiomas aún se aplica.
4. Desea crear un desinfectante para detectar Javascript malicioso ingresado en una aplicación web. El conjunto de cadenas maliciosas es un lenguaje. El conjunto de cadenas entró en los formularios en otro idioma. Desea determinar si la intersección de estos idiomas no está vacía.
5. Monitoreo en tiempo de ejecución de sistemas reactivos y de misión crítica. Desea diseñar un monitor de software que supervise el funcionamiento de su proceso químico o realice un seguimiento de las actualizaciones en una base de datos financiera. Estos son, en esencia, problemas de inclusión e intersección del lenguaje.
6. Reconocimiento de patrones con sus numerosas aplicaciones. Desea detectar patrones en datos genómicos, en texto, en una serie de informes de errores. Estos son problemas en los que se nos dan palabras de un idioma desconocido y tenemos que adivinar el idioma. Estos son problemas de inferencia del lenguaje.
7. Dado un conjunto de documentos XML, desea aplicar ingeniería inversa a un esquema que se aplique a estos documentos. Los documentos XML se pueden idealizar en árboles. Un esquema es entonces una especificación de un lenguaje de árbol y el problema de inferencia de esquema es un problema de inferencia de lenguaje sobre los lenguajes de árbol.
8. Muchas aplicaciones requieren razonamiento aritmético automatizado. Supongamos que fijamos una teoría lógica como la aritmética de Presburger, en la que tenemos los números naturales, la suma y el predicado menor que. Una fórmula con n variables representa un conjunto de vectores n-dimensionales. Un vector es una secuencia de dígitos y puede codificarse como una palabra. Un predicado es entonces un conjunto de palabras; un idioma. Las operaciones lógicas como la conjunción, la disyunción y la negación se convierten en intersección, unión y complemento de lenguajes (la cuantificación existencial es un tipo de proyección).

La reducción indicada anteriormente trata los lenguajes como objetos matemáticos abstractos. Para aplicar estas ideas en la práctica, necesitamos una estructura de datos para representar lenguajes y algoritmos para manipular estas estructuras de datos.

Ingrese autómatas. Los autómatas nos permiten reducir las preguntas sobre objetos matemáticos abstractos, como los lenguajes, a preguntas algorítmicas concretas sobre gráficos etiquetados. Los lenguajes y la teoría de los autómatas, además de una increíble cantidad de aplicaciones prácticas, proporcionan un servicio intelectual muy significativo. Podemos pensar en problemas que van desde formatear códigos postales hasta procedimientos de decisión para la lógica monádica de segundo orden en un espacio conceptual uniforme y ordenado. ¡Qué asombroso es eso!

No he dicho nada sobre lógica y procedimientos de decisión. (Sí, tienen aplicaciones prácticas.) Vea la respuesta de Kaveh para una descripción autorizada.

Como se explicó en las otras respuestas, la teoría de los autómatas es importante conceptualmente como un modelo computacional simple que entendemos bien, y las expresiones regulares y los autómatas tienen muchas aplicaciones de la vida real.

Aquí hay un pequeño ejemplo de investigación moderna que se remonta a la teoría de autómatas para comprender un concepto moderno. En este artículo, los investigadores prueban que todos los lenguajes regulares tienen probadores de propiedades: "Los lenguajes regulares son verificables con un número constante de consultas"

No se trata solo de autómatas de vainilla. Está aprendiendo los conceptos básicos (aceptar estados, transiciones épsilon, ...) de un modelo (computacional) que ayuda a razonar sobre lo que puede y, lo que es más importante, lo que no puede expresarse con algunos lenguajes de consulta. Algunos resultados interesantes incluyen:

• sí, el famoso resultado es que los Autómatas finitos deterministas reconocen los idiomas regulares , por lo que ahora sabe lo que necesita para implementar la coincidencia de expresiones regulares.
• Pushdown Automata reconoce las gramáticas libres de contexto : ahora tiene una idea de cómo se ve un analizador sintáctico (o al menos una gran clase de ellas).
• los autómatas de árbol reconocen las declaraciones sobre la lógica monádica de segundo orden : ahora tiene una idea de lo que se necesita para implementar algunos lenguajes de programación de restricciones, o ... algunas declaraciones en SQL , por ejemplo.

(y, por supuesto, me estoy saltando muchas otras clases)

Básicamente, es un modelo muy general. Sus clases probablemente enfatizarán el vínculo entre autómatas, idiomas y lógica.

Si estuviera buscando relacionar esto con herramientas "mundanas" concretas, pasaría una mañana tranquila en la biblioteca leyendo un par de partes (AB?) De Fundamentos de bases de datos de Abiteboul & al, e intentando conectar esto de nuevo al material de clase . Por supuesto, es solo una de las (muchas) formas de buscar aplicaciones de una clase de autómatas, y supongo que no es la más obvia, pero es precisamente por eso que es un ejercicio interesante.

Como ya se señaló en varias respuestas, la Teoría de Autómatas en los cursos de UG le da a uno el marco conceptual básico para introducir temas más avanzados (y prácticos), y también para señalar conexiones ignoradas; por ejemplo: Diagramas de decisión binarios (son DFA minimizados; después de enseñar DFA, a menudo enseño la resolución de acertijos basada en BDD); secuencias de comandos incluidas en BioPerl y BioPython (y una excelente configuración para reforzar cuántas coincidencias no intencionadas pueden estar ocultas en expresiones regulares de secuencias de comandos del mundo real), depuración formal (propiedades de estado como FA negada, intersección) e incluso VCR o programación de alarma de intrusos domésticos (Todos los días se enfatiza la situación de un autómata mal especificado que se enseña a través de ejemplos incompletos; tal vez se formaliza utilizando la síntesis de interfaces de usuario basada en el escenario play-in / play-out de Harel). También uso la configuración para enseñar Python '

Lanzaré otra respuesta desde un ángulo práctico completamente diferente: las máquinas de estado finito (o al menos algunas generalizaciones / extensiones simples de ellas) a menudo se usan en el lado de la IA de la programación de juegos. Resultan proporcionar un modelo excelente para encapsular el comportamiento de los personajes; por ejemplo, un enemigo puede tener estados que representan 'patrulla', 'búsqueda', 'aproximación', 'ataque', 'defensa', 'retirada', 'muerte', etc. con transiciones bien definidas entre ellos. Esto no involucra ninguno de los aspectos formales de los autómatas, como los lenguajes regulares y similares, pero el concepto del autómata es muy esencial.

Hemos visto que el lenguaje que contrasta la teoría y la práctica, colocando el uno por encima del otro, es la consumación misma de la ignorancia: demuestra que un hombre no está familiarizado con los primeros elementos del pensamiento, y es un gran camino para demostrar su importa ser tan pervertido como para ser incapaz de que se les enseñe.

- James Mill (escribiendo seudónimo como "PQ"), "Teoría y práctica", London and Westminster Review , abril de 1836

Ha habido una considerable investigación relacionada con la teoría de autómatas en la verificación de modelos utilizada en la industria. Consulte las conferencias recientes de Moshe Vardi en el Fields Institute , en particular la tercera conferencia "Lógica, autómatas, juegos y algoritmos" para ver por qué la teoría de autómatas sigue siendo importante y útil.

Abstracto:

El enfoque de teoría de autómatas a los procedimientos de decisión, introducido por Buechi, Elgot, Rabin y Trakhtenbrot en las décadas de 1950 y 1960, es uno de los enfoques más fundamentales para los procedimientos de decisión. Recientemente, este enfoque ha encontrado aplicaciones industriales en la verificación formal de sistemas de hardware y software. El camino de la lógica a los algoritmos prácticos pasa no solo a través de autómatas, sino también a través de juegos, cuyos aspectos algorítmicos fueron estudiados por Chandra, Kozen y Stockmeyer a fines de la década de 1970. En esta charla general, describimos el camino de la lógica a los algoritmos a través de autómatas y juegos.

Las diapositivas y los archivos de audio de las conferencias están disponibles aquí: 1 , 2 , 3 .

Debemos tener en cuenta la semántica de las palabras "práctica" y "aplicación". Para algunos estudiantes, práctico es cualquier cosa que los ayude a aprobar sus exámenes; para otros, cualquier cosa que surja en un trabajo. En ambos casos, la teoría de los autómatas es muy práctica.

Como otros señalan, usará gramáticas, por ejemplo, al estudiar compiladores. Pero aún más que eso: comprender todo el concepto de tener diferentes estados y reglas para las transiciones entre ellos puede hacerte un mejor programador cuando te das cuenta, por ejemplo, de que tu código es redundante aquí y allá, y que cuando lo mejoras, están aplicando en su código las mismas ideas conceptuales detrás de la minimización de DFA.

Del mismo modo para "aplicación". ¿Qué entiendes por esa palabra? Incluso si usted es un "ingeniero con los pies en la tierra", verá y utilizará ideas similares a las de la teoría de autómatas en proyectos del mundo real: código de programación, diagramas de flujo e incluso el concepto simple pero brillante de una pila. Para los nerds de la teoría como yo, considero aplicaciones de la teoría de autómatas en otras áreas, como la lógica, el álgebra y la teoría de modelos finitos. Seguramente, probablemente nunca necesite usar el lema de bombeo cuando compre en un supermercado, pero teoremas como ese me han ayudado a comprender la estructura de ciertas clases de idiomas, sin mencionar las lógicas y las estructuras algebraicas con las que están en correspondencia. Y eso es algo que valoro más que cualquier medida de practicidad.

Junto con la lógica, los autómatas pueden ofrecer formas de verificar estados como

$\qquad A \models \varphi$

para un autómata $A$ y una fórmula $\varphi$. Si$A$ es un modelo de un sistema y $\varphi$ una formalización de las propiedades deseadas obtiene la verificación del sistema, una preocupación muy práctica con un número creciente de aplicaciones factibles.

Tener en cuenta el lado de los autómatas lleva a buenos algoritmos. Por ejemplo, si$\varphi$es una fórmula LTL y$A$ un autómata Büchi (es decir, un autómata finito que se ejecuta infinitamente) que puede traducir $\varphi$ a un autómata equivalente $A_\varphi$ y verifique si $\cal{L}(A) \subseteq \cal{L}(A_\varphi)$

Autómatas finitos, a menudo escritos como máquinas de estados finitos en diferentes contextos, o con sus variantes probabilísticas Los modelos ocultos de Markov se pueden aplicar al reconocimiento de patrones y la estructura cuantitativa de un patrón. Por ejemplo, ¿cuál es el autómata finito estocástico más pequeño que generará cadenas de acuerdo, más o menos, a una distribución de probabilidad dada, o que coincida con las propiedades estadísticas de una muestra de cadenas (o series de tiempo) de alguna distribución.

Ver, por ejemplo , CSSR , un algoritmo para reconstruir ciegamente estados ocultos; Es más eficiente y flexible que los modelos ocultos de Markov.

Otra aplicación más práctica de la teoría de autómatas es el desarrollo de la inteligencia artificial. La inteligencia artificial se desarrolló a partir del concepto de autómata finito. La red neuronal de robots se construye sobre la base de la teoría de autómatas. Después de todos los robots también son autómatas.

Algunos han dado excelentes respuestas cuando se trata de cómo se relaciona con la industria. Lo que debería ser importante es su valor científico, y la teoría de los autómatas es a menudo la puerta de entrada para comprender primero un nivel superior de teoría de la computación en los estudios de un estudiante universitario. La teoría de los autómatas tiene un gran conjunto de teoremas que aparecen por todas partes en Ciencias de la Computación Teórica, y especialmente cuando se quiere hablar sobre aplicaciones como los compiladores. Su valor científico (no está desactualizado, ¿cómo podría serlo? Es la teoría central para el campo) es práctico para cualquier científico que esté interesado en la computación. Es práctico, ya que es un conocimiento que es útil para aquellos que entienden o quieren entender la naturaleza de la computación. Si no puede encontrar uso en él, cuestiono las investigaciones o incluso la intención de estudiar CS ya que no es programación (eso '