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 x se representa mediante una transición .
4. Disyunción (|). Sea la expresión e₁|e₂ 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₁.e₂ o más sencillamente e₁e₂ el 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₁* el AFND-V equivalente toma la forma: donde T(e₁) es el AFND-V resultante de las expresión e₁.
7. Se continúa hasta que no quede ninguna expresión regular que convertir.

Ejemplo

Obtener un autómata finito equivalente a la expresión regular que define a los números enteros sin signo en el lenguaje de programación Python.

Las constantes o literales naturales en Python se definen por la expresión regular:

• 0 | ((1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)

El primer caso es una disyunción que puede esquematizarse como:

• 

Después sigue la concatenación ((1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*) cuya representación queda:

• 

Se continúa, momentáneamente alterando el orden original, con propósitos didácticos, la clausura e₂₂=(0|1|2|3|4|5|6|7|8|9)*:

• 

Luego, se prosigue aplicando el algoritmo a las expresiones e₂₁=1|2|3|4|5|6|7|8|9 y e₂₂₁=0|1|2|3|4|5|6|7|8|9 hasta que se hayan reducido totalmente.

Vease 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.