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

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 de expresiones regulares, en «proyectos prácticos», como un correo electrónico. servidor.

3. Si eres un estudiante de CS, definitivamente estarás escribiendo un compilador / intérprete para un lenguaje (al menos pequeño). Si alguna vez lo has intentado Esta tarea antes y se quedó atascado, apreciará cuánto puede ayudarlo una pequeña teoría (también conocida como gramáticas libres de contexto). Esta teoría ha convertido una tarea que alguna vez fue 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 estudiante de informática, en algún momento, debes sentarte y pensar en los fundamentos filosóficos de la informática, y no casi 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 al 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 Compiler Construction. En 1965, Knuth comenzó el estudio de analizadores sintácticos LR. Rápidamente (en menos de una década), tuvimos analizadores LALR que son un subconjunto de autómatas pushdown deterministas que nos permiten implementar analizadores de cambio / reducción.

En el corazón de la viabilidad y eficiencia del análisis LALR está una prueba (de Knuth) de que los «prefijos» del idioma resultan ser regulares (su autómata finito). Esta es la génesis de los generadores de analizadores sintácticos automatizados 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 llegar a ser?

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

Comentarios

• El análisis de archivos fuente no es realmente la parte interesante (e importante) de un compilador, así que no ‘ No creo que sea seguro decir que los » lenguajes de programación como los conocemos deben gran parte de su eficiencia de compilación a estos desarrollos «. Además, es posible analizar idiomas utilizando diferentes herramientas, por ejemplo, PEG o combinadores de análisis (es decir, parsec).

¿Puedes oír ese ruido ? Es el sonido de mil teoremas, aplicaciones y herramientas brillantes que se ríen en el cielo de la teoría de los autómatas.

Los lenguajes y autómatas son conceptos elegantes y robustos que encontrarás en todas las áreas de la informática. Los lenguajes no son herencias secas y formalistas 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 revolucionario que el álgebra y la topología aportan a las matemáticas clásicas. Aquí hay algunos problemas prácticos, bastante complicados, que se abordan a través de la teoría del lenguaje.

1. Desea detectar apariciones duplicadas de una frase en un documento y eliminar la segunda ocurrencia. En esencia, desea sustituir una secuencia en un idioma.
2. ¿Un programa contiene una infracción de afirmación? ¿Un controlador de dispositivo respeta ciertos protocolos al interactuar con el kernel? 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 la corrección del programa equivale a una verificación de inclusión de lenguaje.
3. ¿Puede su software estar atascado en un bucle infinito? ¿Un algoritmo distribuido contiene un livelock? Necesitamos idiomas en lugar de 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 idioma. El conjunto de cadenas ingresado en los formularios en otro idioma. Desea determinar si la intersección de estos lenguajes 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 rastree las actualizaciones de una base de datos financiera. Estos son problemas fundamentales de inclusión e intersección del lenguaje.
6. Reconocimiento de patrones con sus numerosas aplicaciones. Quiere 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 de 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 como á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 lenguajes de árbol.
8. Muchas aplicaciones requieren razonamiento aritmético automatizado. Supongamos que arreglamos 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 de n dimensiones. Un vector es una secuencia de dígitos y se puede codificar como una palabra. Un predicado es entonces un conjunto de palabras; un idioma. Operaciones lógicas como conjunción, disyunción y negación se convierten en intersección, unión y complemento de lenguajes (la cuantificación existencial es una especie de proyección).

La reducción insinuada anteriormente trata a 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.

Introduzca 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 autómatas, además de una enorme cantidad de aplicaciones prácticas, brindan 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 despejado. ¡Qué asombroso es eso!

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

Comentarios

• jaja, la ironía

Como se explicó en las otras respuestas, la teoría de autómatas es importante conceptualmente como un modelo computacional simple que entendemos bien, y las expresiones regulares y los autómatas tienen muchas aplicaciones en 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 demuestran que todos los lenguajes regulares tienen probadores de propiedades: «Los lenguajes regulares se pueden probar con un número constante de consultas»

Como ya se señaló en varias respuestas, la Teoría de Autómatas en los cursos de UG brinda el marco conceptual básico para introducir temas más avanzados (y prácticos), y también por señalar conexiones pasadas por alto; por ejemplo: Diagramas de decisión binarios (son DFA minimizados; después de enseñar DFA, a menudo enseño resolución de acertijos basada en BDD); secuencias de comandos incluidas en BioPerl y BioPython (y un gran entorno en el que reforzar la cantidad de coincidencias no deseadas pueden estar ocultas en expresiones regulares de secuencias de comandos del mundo real), depuración formal (propiedades del estado como FA negada, intersección) e incluso VCR o programación de alarma de intrusión en el hogar (situación de estrés diario de un autómata mal especificado enseñado a través de ejemplos incompletos; tal vez formalizado usando la síntesis de interfaces de usuario basada en escenarios de entrada / salida de Harel). También utilizo la configuración para enseñar Python (casi) puramente subconjunto funcional, que incluye mapas, lambdas y comprensiones de conjuntos, utilizando los cuales se pueden codificar algoritmos estándar de FA, a menudo de una manera prácticamente indistinguible de las definiciones matemáticas.

Comentarios

• ¡Bienvenido, Ganesh!
• Una buena forma de enseñar a los autómatas. ¿Estarías dispuesto a compartir tus notas de clase?

Se han realizado investigaciones considerables relacionadas con la teoría de los autómatas. en la verificación de modelos utilizados 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 los autómatas es sigue siendo importante y útil.

Resumen:

El enfoque teórico de los autómatas para los procedimientos de decisión, presentado 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 no solo pasa por los 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 desde 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 .

Lanzaré otra respuesta desde un ángulo práctico completamente diferente: las máquinas de estados finitos (o al menos algunas generalizaciones / extensiones simples de ellas) se usan a menudo en la IA lado de la programación del juego. Resultan proporcionar un modelo excelente para encapsular el comportamiento de los personajes; por ejemplo, un enemigo puede tener estados que representen «patrullar», «buscar», «acercarse», «atacar», «defender», «retirarse», «morir», etc. con transiciones bien definidas entre ellos. Esto no implica ninguno de los aspectos formales de los autómatas como los lenguajes regulares y similares, pero el concepto del autómata es muy básico.

Hemos visto que el lenguaje que contrasta teoría y práctica, colocando una sobre la otra, es la consumación de ignorancia, que demuestra que un hombre no está familiarizado con los primeros elementos del pensamiento, y hace un gran camino para probar que su mente está tan pervertida que es incapaz de ser enseñada.

– James Mill (escrito de forma seudónima como» PQ”),“ Theory and Practice ”, London and Westminster Review , abril de 1836

Debemos tener en cuenta la semántica de las palabras «práctica» y «aplicación». Para algunos estudiantes, práctico es cualquier cosa que les 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 señalan otros, utilizará gramáticas, por ejemplo, al estudiar compiladores. Pero incluso más que eso: comprender todo el concepto de tener diferentes estados y reglas para las transiciones entre ellos puede convertirlo en un mejor programador cuando se da cuenta, por ejemplo, de que su código es redundante aquí y allá, y que cuando lo mejora, 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 eres un «ingeniero con los pies en la tierra», verás y usarás ideas similares a las de la teoría de los 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 los autómatas en otras áreas, como lógica, álgebra y teoría de modelos finitos. Seguramente, probablemente nunca necesitaré usar el lema de bombeo mientras compro en un supermercado, pero teoremas como ese me han ayudado a comprender la estructura de ciertas clases de lenguajes, sin mencionar las estructuras lógicas y algebraicas con las que se corresponden. Y eso es algo que valoro más que cualquier medida de practicidad.

Junto con las lógicas, los autómatas pueden ofrecer formas de compruebe enunciados 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 viables.

Considerando el lado de los autómatas de las cosas conduce a buenos algoritmos. Por ejemplo, si $ \ varphi $ es una fórmula LTL y $ A $ a autómata Büchi (es decir, un autómata finito de ejecución infinita), 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 descritos 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 de cuantificación de un patrón. P.ej. ¿Cuál es el autómata finito estocástico más pequeño que generará cadenas de acuerdo, más o menos, con una distribución de probabilidad dada, o propiedades estadísticas coincidentes de una muestra de cadenas (o series de tiempo) de alguna distribución?

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

Comentarios

• Para agregar al lado práctico, los modelos ocultos de Markov se utilizan en el reconocimiento de voz programas como Kurzweil.

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 los robots se construye sobre la base de la teoría de los autómatas. Después de todo, 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 suele ser la puerta para comprender primero un nivel superior de teoría de la computación. en los estudios de un estudiante de pregrado. La teoría de los autómatas tiene un gran conjunto de teoremas que aparecen por todas partes en la informática teórica, y especialmente cuando se quiere hablar de aplicaciones como los compiladores. Su valor científico (no está desactualizado, ¿cómo podría serlo? Es la teoría central del campo) es práctico para cualquier científico interesado en la computación. Es práctico, ya que es un conocimiento que es útil para aquellos que entienden o quieren para comprender la naturaleza de la computación. Si no puede encontrarle uso, cuestiono la investigación de uno o incluso la intención de estudiar la informática, ya que no es programación (es una aplicación de la informática), es una ciencia formal.