Algoritmo de Thompson
Thompson's construction algorithm
- Fecha
- 1968 · fiabilidad media
- Lugar
- Murray Hill, Nueva Jersey, Estados Unidos
- Autoría
- Ken Thompson
- Ámbito
- Saber y símbolos
Qué es
Algoritmo, también llamado construcción de McNaughton-Yamada-Thompson, que transforma una expresión regular en un autómata finito no determinista (AFN) equivalente, permitiendo compilar patrones de búsqueda de texto en máquinas ejecutables.
A qué dio paso
- base de los motores de expresiones regulares en editores de texto y compiladores
- la herramienta grep, desarrollada por el propio Thompson
- estándar en la teoría de lenguajes formales y en el diseño de compiladores
- influencia en el diseño de Unix y sus herramientas de texto