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 e1|e2 el AFND-V equivalente toma la forma: donde T(e1) y T(e2) son los AFND-V resultantes de las expresiones e1 y e2respectivamente.
  5. Concatenación (.). Sea la expresión e1.e2 o más sencillamente e1e2 el AFND-V equivalente toma la forma: donde T(e1) y T(e2) son los AFND-V resultantes de las expresiones e1 y e2. Tras la concatenación normalmente T(e1) pierde sus estados finales para dejar sólo los de T(e2).
  6. Clausura (*). Sea la expresión e1* el AFND-V equivalente toma la forma: donde T(e1) es el AFND-V resultante de las expresión e1.
  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 e22=(0|1|2|3|4|5|6|7|8|9)*:

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

Vease también

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.
This article is issued from Ecured. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.