¿No sabes por dónde empezar? Ayúdanos normalizando artículos.
¿Tienes experiencia? Crea alguno de estos artículos de actualidad.

Diferencia entre revisiones de «Algoritmo de Thompson»

Línea 8: Línea 8:
 
# Se coloca el estado inicial ''Q0'':[[Archivo:AF_Estado_Inicio.gif|middle]].
 
# Se coloca el estado inicial ''Q0'':[[Archivo:AF_Estado_Inicio.gif|middle]].
 
# Si la expresión admite la cadena vacía, ''Q0'' se indica como un estado final: [[Archivo:AF_Estado_Inicio_Final.gif|middle]]
 
# Si la expresión admite la cadena vacía, ''Q0'' se indica como un estado final: [[Archivo:AF_Estado_Inicio_Final.gif|middle]]
# Cada símbolo terminal se representa mediante una transición [[Archivo:AFD_Transicion.gif|middle]].
+
# Cada símbolo terminal ''x'' se representa mediante una transición [[Archivo:AFD_Transicion.gif|middle]].
# '''Disjunción'''. Sea la expresión ''e<sub>1</sub>|e<sub>2</sub>'' el AFND-V equivalente toma la forma:[[Archivo:Thompson_Disjuncion.gif|middle]] donde ''T(e<sub>1</sub>)'' y ''T(e<sub>2</sub>)'' son los AFND-V resultantes de las expresiones ''e<sub>1</sub>'' y ''e<sub>2</sub>''respectivamente.
+
# '''Disyunción (|)'''. Sea la expresión ''e<sub>1</sub>|e<sub>2</sub>'' el AFND-V equivalente toma la forma:[[Archivo:Thompson_Disjuncion.gif|middle]] donde ''T(e<sub>1</sub>)'' y ''T(e<sub>2</sub>)'' son los AFND-V resultantes de las expresiones ''e<sub>1</sub>'' y ''e<sub>2</sub>''respectivamente.
 
# '''Concatenación (.)'''. Sea la expresión ''e<sub>1</sub>.e<sub>2</sub>'' o más sencillamente ''e<sub>1</sub>e<sub>2</sub>'' el AFND-V equivalente toma la forma:[[Archivo:Thompson_Concatenacion.gif|middle]] donde ''T(e<sub>1</sub>)'' y ''T(e<sub>2</sub>)'' son los AFND-V resultantes de las expresiones ''e<sub>1</sub>'' y ''e<sub>2</sub>''. Tras la concatenación normalmente ''T(e<sub>1</sub>)'' pierde sus estados finales para dejar sólo los de ''T(e<sub>2</sub>)''.
 
# '''Concatenación (.)'''. Sea la expresión ''e<sub>1</sub>.e<sub>2</sub>'' o más sencillamente ''e<sub>1</sub>e<sub>2</sub>'' el AFND-V equivalente toma la forma:[[Archivo:Thompson_Concatenacion.gif|middle]] donde ''T(e<sub>1</sub>)'' y ''T(e<sub>2</sub>)'' son los AFND-V resultantes de las expresiones ''e<sub>1</sub>'' y ''e<sub>2</sub>''. Tras la concatenación normalmente ''T(e<sub>1</sub>)'' pierde sus estados finales para dejar sólo los de ''T(e<sub>2</sub>)''.
 
# '''Clausura (*)'''. Sea la expresión ''e<sub>1</sub>*'' el AFND-V equivalente toma la forma:[[Archivo:Thompson_Clausura.gif|middle]] donde ''T(e<sub>1</sub>)'' es el AFND-V resultante de las expresión ''e<sub>1</sub>''.
 
# '''Clausura (*)'''. Sea la expresión ''e<sub>1</sub>*'' el AFND-V equivalente toma la forma:[[Archivo:Thompson_Clausura.gif|middle]] donde ''T(e<sub>1</sub>)'' es el AFND-V resultante de las expresión ''e<sub>1</sub>''.
 +
# 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úmero entero|números enteros]] sin signo en el [[lenguaje de programación]] [[Python]].
 +
 +
Las constantes o literales [[número natural|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:
 +
 +
* [[Archivo:Thompson_Ejemplo_1_Disjuncion_Inicial.gif|middle]]
 +
 +
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:
 +
 +
* [[Archivo:Thompson_Ejemplo_1_Concatenacion.gif|middle]]
 +
 +
Se continúa, momentáneamente alterando el orden original, con propósitos didácticos, la clausura ''(0|1|2|3|4|5|6|7|8|9)*'':
 +
 +
* [[Archivo:Thompson_Ejemplo_1_Clausura.gif|middle]]
 +
 +
Luego, se prosigue aplicando el algoritmo a las expresiones ''1|2|3|4|5|6|7|8|9'' y ''0|1|2|3|4|5|6|7|8|9''hasta que se hayan reducido totalmente.
  
 
==Vease también==
 
==Vease también==

Revisión del 19:30 30 nov 2013

Algoritmo de Thompson
Información sobre la plantilla
NoAFND.png
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:AF Estado Inicio.gif.
  2. Si la expresión admite la cadena vacía, Q0 se indica como un estado final: AF Estado Inicio Final.gif
  3. Cada símbolo terminal x se representa mediante una transición AFD Transicion.gif.
  4. Disyunción (|). Sea la expresión e1|e2 el AFND-V equivalente toma la forma:Thompson Disjuncion.gif 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:Thompson Concatenacion.gif 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:Thompson Clausura.gif 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:

  • Thompson Ejemplo 1 Disjuncion Inicial.gif

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:

  • Thompson Ejemplo 1 Concatenacion.gif

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

  • Thompson Ejemplo 1 Clausura.gif

Luego, se prosigue aplicando el algoritmo a las expresiones 1|2|3|4|5|6|7|8|9 y 0|1|2|3|4|5|6|7|8|9hasta 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.