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 equivalente (NFA). [2] Este NFA se puede utilizar para hacer coincidir cadenas con la expresión regular. Este algoritmo se le 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 avanzada, pero las NFA son más adecuadas para su ejecución en una computadora. Por lo tanto, este algoritmo es de interés práctico, ya que puede compilar expresiones regulares en NFA. Desde un punto de vista teórico, este algoritmo es parte de la prueba de que ambos aceptan exactamente los mismos lenguajes, es decir, los lenguajes regulares .
Un 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. Sin embargo, una NFA también se puede interpretar directamente .
Para decidir si dos expresiones regulares dadas describen el mismo lenguaje, cada una se puede convertir en un autómata finito determinista mínimo equivalente mediante la construcción de Thompson, la construcción del conjunto de potencias y la minimización de DFA . Si, y solo si, los autómatas resultantes aceptan el cambio de nombre de los estados, los lenguajes de las expresiones regulares están de acuerdo.
El algoritmo
El algoritmo funciona de forma recursiva dividiendo una expresión en sus subexpresiones constituyentes, a partir de las cuales se construirá el NFA 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 Δ [ aclaración necesaria ] respeta las siguientes propiedades:
- A tiene exactamente un estado inicial q 0 , que no es accesible desde ningún otro estado. Es decir, para cualquier estado q y cualquier letra a ,no contiene q 0 .
- A tiene exactamente un estado final q f , que no es co-accesible desde ningún otro estado. Es decir, para cualquier letra a ,.
- Sea c el número de concatenación de la expresión regular E y sea s el número de símbolos sin paréntesis, es decir, | , * , Una 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 salen de cualquier estado es como máximo dos.
- Dado que un NFA de m estados y como máximo e transiciones de cada estado pueden coincidir con una cadena de longitud n en el tiempo O ( emn ) , un NFA de Thompson puede hacer coincidir patrones en tiempo lineal, asumiendo un alfabeto de tamaño fijo. [4] [se necesita una mejor fuente ]
Reglas
Las siguientes reglas se describen de acuerdo con Aho et al. (2007), [1] pág. 122. En lo que sigue, N ( s ) y N ( t ) son el NFA de las subexpresiones s y t , respectivamente.
La expresión vacía ε se convierte en
Un símbolo a del alfabeto de entrada se convierte en
La expresión sindical s | t se convierte en
El estado q pasa por ε al estado inicial de N ( s ) o N ( t ). Sus estados finales se convierten en estados intermedios de todo el NFA y se fusionan a través de dos transiciones ε en el estado final del NFA.
La expresión de concatenación st se convierte en
El estado inicial de N ( s ) es el estado inicial de todo el NFA. El estado final de N ( s ) se convierte en el estado inicial de N ( t ). El estado final de N ( t ) es el estado final de todo el NFA.
La expresión de la estrella de Kleene s * se convierte en
Una transición ε conecta el estado inicial y final del NFA con el ( los ) N ( s ) sub-NFA en el medio. Otra ε-transición del estado final interno al inicial interno de N ( s ) permite la repetición de la expresión s según el operador en estrella.
- La expresión entre paréntesis ( s ) se convierte en N ( s ) en sí.
Con estas reglas, usando la expresión vacía y las reglas de símbolo como casos base, es posible probar con inducción matemática que cualquier expresión regular puede convertirse en un NFA equivalente. [1]
Ejemplo
Ahora se dan dos ejemplos, uno pequeño informal con el resultado y otro más grande con una aplicación paso a paso del algoritmo.
Pequeño ejemplo
La siguiente imagen muestra el resultado de la construcción de Thompson en (ε|a*b)
. El óvalo púrpura 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 en 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 de sintaxis) de la expresión, con "." que denota concatenación (se supone que tiene aridad variable); las subexpresiones se denominan a - q para fines de 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 coloreada en magenta y cian , respectivamente. Se omite una etiqueta de transición ε como para mayor claridad; las transiciones sin etiquetar son, de hecho, transiciones ε. El estado de entrada y salida correspondiente a la expresión raíz q es el estado de inicio y aceptación del autómata, respectivamente.
Los pasos del algoritmo son los siguientes:
q : | empezar a convertir la expresión de la estrella de Kleene | (0|(1(01*(00)*0)*1)*)* | ||||||||
b : | comenzar a convertir la expresión de unión | 0|(1(01*(00)*0)*1)* | ||||||||
a : | convertir símbolo | 0 | ||||||||
p : | empezar a convertir la expresión de la estrella de Kleene | (1(01*(00)*0)*1)* | ||||||||
d : | comenzar a convertir la expresión de concatenación | 1(01*(00)*0)*1 | ||||||||
c : | convertir símbolo | 1 | ||||||||
n : | empezar a convertir la expresión de la estrella de Kleene | (01*(00)*0)* | ||||||||
f : | comenzar a convertir la expresión de concatenación | 01*(00)*0 | ||||||||
e : | convertir símbolo | 0 | ||||||||
h : | empezar a convertir la expresión de la estrella de Kleene | 1* | ||||||||
g : | convertir símbolo | 1 | ||||||||
h : | terminó de convertir la expresión de la estrella de Kleene | 1* | ||||||||
l : | empezar a convertir la expresión de la estrella de Kleene | (00)* | ||||||||
j : | comenzar a convertir la expresión de concatenación | 00 | ||||||||
yo : | convertir símbolo | 0 | ||||||||
k : | convertir símbolo | 0 | ||||||||
j : | terminó de convertir la expresión de concatenación | 00 | ||||||||
l : | terminó de convertir la expresión de la estrella de Kleene | (00)* | ||||||||
m : | convertir símbolo | 0 | ||||||||
f : | terminó de convertir la expresión de concatenación | 01*(00)*0 | ||||||||
n : | terminó de convertir la expresión de la estrella de Kleene | (01*(00)*0)* | ||||||||
o : | convertir símbolo | 1 | ||||||||
d : | terminó de convertir la expresión de concatenación | 1(01*(00)*0)*1 | ||||||||
p : | terminó de convertir la expresión de la estrella de Kleene | (1(01*(00)*0)*1)* | ||||||||
b : | terminó de convertir la expresión de unión | 0|(1(01*(00)*0)*1)* | ||||||||
q : | terminó de convertir la expresión de la estrella de Kleene | (0|(1(01*(00)*0)*1)*)* |
A continuación se muestra un autómata determinista mínimo equivalente.
Relación con otros algoritmos
El de Thompson es uno de varios algoritmos para construir NFA a partir de expresiones regulares; [5] McNaughton y Yamada dieron un algoritmo anterior. [6] Contrario a 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 a la construcción de Thompson, una vez que se eliminan las transiciones ε.
Referencias
- ^ a b c Alfred Vaino Aho ; Monica S. Lam ; Ravi Sethi ; Jeffrey D. Ullman (2007). "3.7.4 Construcción de una NFA a partir de una expresión regular" (impresión) . Compiladores: principios, técnicas y herramientas (2ª ed.). Boston, MA, EE.UU .: Pearson Addison-Wesley. pag. 159-163 . ISBN 9780321486813.
- ^ Louden, Kenneth C. (1997). "2.4.1 De una expresión regular a una NFA" (imprimir) . Construcción del compilador: Principios y práctica (3ª ed.). 20 Park Plaza Boston, MA 02116-4324, EE.UU .: PWS Publishing Company. págs. 64–69. ISBN 978-0-534-93972-4.Mantenimiento de CS1: ubicación ( enlace )
- ^ Ken Thompson (junio de 1968). "Técnicas de programación: algoritmo de búsqueda de expresiones regulares". Comunicaciones de la ACM . 11 (6): 419–422. doi : 10.1145 / 363347.363387 .
- ^ Xing, Guangming. "Minimizado Thompson NFA" (PDF) .
- ^ Watson, Bruce W. (1995). Una taxonomía de algoritmos de construcción de autómatas finitos (PDF) (Informe técnico). Universidad Tecnológica de Eindhoven . Informe sobre ciencias de la computación 93/43.
- ^ R. McNaughton, H. Yamada (marzo de 1960). "Expresiones regulares y gráficos de estado para autómatas". Transacciones IEEE en computadoras electrónicas . 9 (1): 39–47. doi : 10.1109 / TEC.1960.5221603 .