La construcción de Thompson

En informática , el algoritmo de construcción de Thompson , también llamado algoritmo de McNaughton-Yamada-Thompson , ^{[ 1 ]} es un método para transformar una expresión regular en un autómata finito no determinista (AFN) equivalente. ^{[ 2 ]} Este AFN se puede usar para comparar cadenas con la expresión regular. Este algoritmo se atribuye a Ken Thompson .

Las expresiones regulares y los autómatas finitos no deterministas son dos representaciones de lenguajes formales . Por ejemplo, las utilidades de procesamiento de texto utilizan expresiones regulares para describir patrones de búsqueda avanzados, pero los autómatas finitos no deterministas son más adecuados para su ejecución en una computadora. Por lo tanto, este algoritmo tiene interés práctico, ya que puede compilar expresiones regulares en autómatas finitos no deterministas. Desde un punto de vista teórico, este algoritmo forma parte de la prueba de que ambos aceptan exactamente los mismos lenguajes, es decir, los lenguajes regulares .

Un autómata finito no determinista (AFND) puede hacerse determinista mediante la construcción del conjunto potencia y luego minimizarse para obtener un autómata óptimo que corresponda a la expresión regular dada. Sin embargo, un AFND también puede interpretarse directamente .

Para determinar si dos expresiones regulares describen el mismo lenguaje, cada una puede convertirse en un autómata finito determinista mínimo equivalente mediante la construcción de Thompson, la construcción de conjuntos potencia y la minimización de autómatas finitos deterministas (AFD) . Si, y solo si, los autómatas resultantes coinciden salvo por el cambio de nombre de los estados, los lenguajes de las expresiones regulares coinciden.

El algoritmo funciona recursivamente dividiendo una expresión en sus subexpresiones constituyentes, a partir de las cuales se construirá el autómata finito no determinista (AFND) utilizando un conjunto de reglas. ^{[ 3 ]} Más precisamente, a partir de una expresión regular E , el autómata A obtenido con la función de transición Δ respeta las siguientes propiedades:

• A tiene exactamente un estado inicial q ₀ , que no es accesible desde ningún otro estado. Es decir, para cualquier estado q y cualquier letra a ,${\displaystyle \Delta (q,a)}$no contiene q ₀ .
• A tiene exactamente un estado final q _f , que no es coaccesible desde ningún otro estado. Es decir, para cualquier letra a ,${\displaystyle \Delta (q_{f},a)=\emptyset }$.
• Sea c el número de concatenaciones de la expresión regular E y sea s el número de símbolos aparte de los paréntesis, es decir, | , * , a y ε . Entonces, el número de estados de A es 2 s − c (lineal en el tamaño de E ).
• El número de transiciones que parten de cualquier estado es como máximo dos.
• Dado que un autómata finito no determinista (AFND) de m estados y como máximo e transiciones desde cada estado puede coincidir con una cadena de longitud n en tiempo O ( emn ) , un AFND de Thompson puede realizar la coincidencia de patrones en tiempo lineal, suponiendo un alfabeto de tamaño fijo. ^{[ 4 ]}

A continuación se presentan dos ejemplos: uno breve e informal con el resultado, y otro más extenso con la aplicación paso a paso del algoritmo.

Pequeño ejemplo

La imagen a continuación muestra el resultado de la construcción de Thompson en (ε|a*b). El óvalo morado corresponde a a , el óvalo verde azulado corresponde a a* , el óvalo verde corresponde a b , el óvalo naranja corresponde a a*b , y el óvalo azul corresponde a ε .

Aplicación del algoritmo

Como ejemplo, la imagen muestra el resultado del algoritmo de construcción de Thompson sobre la expresión regular (0|(1(01*(00)*0)*1)*)*que denota el conjunto de números binarios que son múltiplos de 3:

{ ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ... }.

La parte superior derecha muestra la estructura lógica (árbol sintáctico) de la expresión, donde "." denota concatenación (con aridad variable); las subexpresiones se denominan de la a a la q para facilitar la referencia. La parte izquierda muestra el autómata finito no determinista resultante del algoritmo de Thompson, con el estado de entrada y salida de cada subexpresión coloreado en magenta y cian , respectivamente. Se omite la etiqueta de transición ε para mayor claridad ; las transiciones sin etiqueta son, de hecho, transiciones ε. El estado de entrada y salida correspondiente a la expresión raíz q es el estado de inicio y de aceptación del autómata, respectivamente.

Los pasos del algoritmo son los siguientes:

A continuación se muestra un autómata determinista mínimo equivalente.

El algoritmo de Thompson es uno de varios algoritmos para construir autómatas finitos no deterministas (AFND) a partir de expresiones regulares; ^{[ 5 ]} McNaughton y Yamada presentaron un algoritmo anterior. ^{[ 6 ]} A diferencia de la construcción de Thompson, el algoritmo de Kleene transforma un autómata finito en una expresión regular.

El algoritmo de construcción de Glushkov es similar al de Thompson, una vez eliminadas las transiciones ε.

Las expresiones regulares se utilizan a menudo para especificar patrones que luego se le pide al software que haga coincidir. Generando un NFA mediante la construcción de Thompson y utilizando un algoritmo apropiado para simularlo, es posible crear software de coincidencia de patrones con un rendimiento que es${\displaystyle O(mn)}$donde m es la longitud de la expresión regular y n es la longitud de la cadena que se compara. Esto es mucho mejor que lo que logran muchas implementaciones de lenguajes de programación populares;[ ^{7 ] sin} embargo, se limita a expresiones puramente regulares y no admite patrones para lenguajes no regulares como las retroreferencias.