Algoritmo de Thompson

Algoritmo de Thompson Concepto: Algoritmo para obtener AFND-V a partir de expresiones regulares.

Algoritmo de Thompson. Algoritmo que permite a partir de una expresión regular obtener un autómata finito no determinista con transiciones vacías (AFND-V) equivalente.

Definición

Sea una expresión regular E se recorre la misma según el orden de precedencia operacional (*, ., |) y los agrupadores para obtener un AFND-V definido por su diagrama de estado según los pasos:

1. Se coloca el estado inicial Q0:.
2. Si la expresión admite la cadena vacía, Q0 se indica como un estado final:
3. Cada símbolo terminal se representa mediante una transición .
4. Disjunción. Sea la expresión e_1|e2 el AFND-V equivalente toma la forma: donde T(e₁₎ y T(e₂₎ son los AFND-V resultantes de las expresiones e₁ y e₂respectivamente.
5. Concatenación (.). Sea la expresión e_1.e2 o simplemente e_1e2el AFND-V equivalente toma la forma: donde T(e₁₎ y T(e₂₎ son los AFND-V resultantes de las expresiones e₁ y e₂. Tras la concatenación normalmente T(e₁₎ pierde sus estados finales para dejar sólo los de T(e₂₎.
6. Clausura (*). Sea la expresión e_1* el AFND-V equivalente toma la forma: donde T(e₁₎ es el AFND-V resultante de las expresión e₁.

Véase también

• Expresión regular.
• Diagrama de estados.
• Autómata finito no determinista con transición vacía.

Fuentes

1. Tanembaum, A. Compilers: Principles, Tecniques, and Tools. Tomo 1. ACM Press. 5ta Edición.
2. Conferencias de la Asignatura "Compilación 1" del Departamento de Ciencias de la Computación de la Universidad de Oriente. Santiago de Cuba, 2000.
3. Autómata finito en Wikipedia. Consultado el 25 de noviembre de 2013.
4. Acevedo Martínez, Liesner; Osorio Ramírez, Karel. Manual de apoyo a la docencia. Técnicas de Compilación: Manual Práctico para estudiantes de Informática. Libro electrónico en PDF. UCI. La Habana, 2011.
5. Algoritmo de Thompson en Wikipedia. Consultado el 30 de noviembre de 2013.