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. Concatenación. Cada símbolo terminal se representa mediante una transición .
4. Clausura (*).
5. Clausura positiva (+).
6. Disjunción (|).

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.