computer-science - programming - finite state machine
¿Está muerta la teoría de los autómatas? (9)
Creo que a medida que se abren nuevas áreas de la computación, como la computación cuántica y la hypercomputation , habrá nuevos requisitos, requisitos y aplicaciones teóricas de la teoría de autómatas y cosas como autómatas evolutivos y computación, autómatas celulares y demás.
No creo que esté muerto, solo un poco frío por el momento.
Me encantó el curso que tomé en Teoría de autómatas y lenguajes formales, así que, naturalmente, comencé a buscar en las interwebs para saber qué sucedió desde el momento en que se escribieron los libros en los que se basó el curso.
Lo que descubrí fue que la lista de cosas con las que no estaba familiarizada parecía ser muy corta. Por ejemplo, de la lista de autómatas en la entrada de Wikipedia para el tema, la mitad estaba cubierta por el curso y la otra mitad estaba relacionada en su mayor parte con el único idioma que no estaba incluido en el curso.
Además, al investigar sobre las aplicaciones de la teoría, obtuve la mayoría de los mismos resultados: sintaxis de lenguaje de programación, compiladores, búsqueda de texto y ... eso es todo.
Entonces, ¿es realmente así de muerto? ¿O sigue evolucionando? ¿Hay nuevas aplicaciones para la teoría?
Creo que la teoría de autómatas está involucrada en muchas áreas sin que la gente se dé cuenta. Por ejemplo, puedo ver su aplicación en criptografía y criptoanálisis.
Eche un vistazo a los procesos de flujo de trabajo y vea cómo la teoría de autómatas podría utilizarse para formalizar los conceptos y patrones descritos: Patrones de flujo de trabajo
En lugar de ver la teoría como muerta, en lugar de eso, considere que se ha vuelto tan práctica para las aplicaciones que hemos ido más allá de la teoría. Un excelente libro para considerar que los puentes entre la teoría y la aplicación son " Practical Statecharts in C / C ++ " de Miro Samek. Ahora hay una segunda edición disponible, que no he leído. Pero no me ha faltado nada en la primera edición; A día de hoy, lo considero uno de los textos más valiosos que he leído.
Los autómatas y los lenguajes formales son la base de las expresiones regulares, analizadores, compiladores, máquinas virtuales, etc. que mejoran regularmente.
También se requieren en el dominio del generador de teoremas para la verificación de programas, cuyo objetivo es probar que un programa o protocolo logra lo que pretende hacer. Este dominio es crítico (software de máquina de votación, transacciones bancarias, sistemas de seguridad en vehículos, etc.) y aún está en desarrollo.
¡Así que no, la teoría de los autómatas y los lenguajes formales no están muertos!
Los automatismos son realmente útiles. Terminé mi licenciatura en ingeniería de software y ciencias de la computación hace casi 20 años. Uno de los primeros cursos fue Modelos de máquinas, que cubría FSA y se aventuró un poco en máquinas de torneado, computabilidad, problemas de detención, etc.
Todos pensaron que el curso era aburrido, irrelevante, demasiado difícil o sin sentido. Los círculos y los arcos no tienen mucho sentido para nadie, y ¿para qué sirve una cinta con solo unos en ella? ¿Qué pasa con un disco duro? Al final del curso, el profesor dio un cuestionario: ¿qué tan útil cree usted que será este curso en un mes, en un año, en diez años? Entonces, respondí no útil para todos ellos. Ahora aumentaría la utilidad con el tiempo y terminaría con "muy útil".
He usado lotes de autómatas en mi trabajo diario, y son la herramienta adecuada para ciertas clases de problemas, con poco más para competir con ellos. Los he usado para comprimir listas de palabras multimillonarias + datos de categoría (ok, bastante banal), y también he implementado una extensión donde los símbolos son objetos complejos y las transiciones de estado son predicados. Esto permitió compilar un conjunto complejo de reglas a un FST determinista y todas las reglas se evaluaron de manera simultánea y determinista sin cómputo redundante.
¡Mi voto es todavía relevante!
No está muerto, sino más "puesto a prueba": es un formalismo simple que se usa más como base para otros, en lugar de ser un tema de investigación particularmente activo.
El trabajo de Henry Thompson sobre esquemas XML utiliza y amplía la teoría de autómatas.
Muchos proyectos de software integrado hacen un uso intensivo de las máquinas de estados finitos, que están relacionadas con los autómatas, y algunas de las técnicas para trabajar con ellas se basan en la teoría de los autómatas o la extienden.
Pi-calculus extiende la teoría de autómatas con el concepto de bisimulación y agrega capacidades para analizar procesos concurrentes. Es la parte más cercana de la investigación reciente a la teoría de autómatas que aprendí en la universidad.
Un montón de cosas de control de proceso se basa en gran medida en la teoría. Especialmente en términos de probar la robustez de los sistemas de control.
Una de las nuevas técnicas que encontré hace unos años se llama Parsing Expression Grammars, también conocido como PEG, también conocido como Packrat Parsing. Bryan Ford ha realizado un trabajo en él que puede verse en http://pdos.csail.mit.edu/~baford/packrat/ .
Básicamente, se trata de un analizador descendente recursivo descendente, y una de sus ventajas es que el análisis léxico y el análisis semántico se pueden realizar en un solo paso.
Los PEG se comparan con los CFG en la medida en que los PEG son más adecuados para analizar un lenguaje libre de contexto, mientras que los CFG son más adecuados para generar un lenguaje libre de contexto.