Algoritmo de construcción de Glushkov
En la teoría de la informática , particularmente en la teoría del lenguaje formal , el algoritmo de construcción de Glushkov , inventado por Victor Mikhailovich Glushkov , transforma una expresión regular dada en un autómata finito no determinista equivalente (NFA). Así, forma un puente entre las expresiones regulares y los autómatas finitos no deterministas: dos representaciones abstractas de la misma clase de lenguajes formales .
Se puede usar una expresión regular para describir convenientemente un patrón de búsqueda avanzada en una operación similar a "buscar y reemplazar" de una utilidad de procesamiento de texto . El algoritmo de Glushkov se puede utilizar para transformarlo en un NFA, que además es pequeño por naturaleza, ya que el número de sus estados es igual al número de símbolos de la expresión regular, más uno. Posteriormente, el NFA puede hacerse determinista mediante la construcción del conjunto de potencias y luego minimizarse para obtener un autómata óptimo correspondiente a la expresión regular dada. El último formato es el más adecuado para la ejecución en una computadora.
Desde otro punto de vista más teórico, el algoritmo de Glushkov es parte de la prueba de que NFA y las expresiones regulares aceptan exactamente los mismos lenguajes; es decir, los lenguajes regulares . El inverso del algoritmo de Glushkov es el algoritmo de Kleene , que transforma un autómata finito en una expresión regular. El autómata obtenido por la construcción de Glushkov es el mismo que el obtenido por el algoritmo de construcción de Thompson , una vez eliminadas sus transiciones ε.
Dada una expresión regular e , el algoritmo de construcción de Glushkov crea un autómata no determinista que acepta el lenguaje aceptado por e . [1] [2] : 59–61 La construcción utiliza cuatro pasos:
Linealización de la expresión. Se cambia el nombre de cada letra del alfabeto que aparece en la expresión e , de modo que cada letra aparece como máximo una vez en la nueva expresión . La construcción de Glushkov se basa esencialmente en el hecho de que representa un idioma local . Sea A el antiguo alfabeto y sea B el nuevo.
