Diferencia entre revisiones de «Algoritmo de Thompson»
(Página creada con '{{Definición|nombre=Algoritmo de Thompson|imagen=noAFND.png|concepto=Algoritmo para obtener AFND-V a partir de expresiones regulares.}} <div align="justify"> '''Algoritmo de Th...') |
m (Texto reemplazado: «<div align="justify">» por «») |
||
| (No se muestran 8 ediciones intermedias de 3 usuarios) | |||
| Línea 1: | Línea 1: | ||
{{Definición|nombre=Algoritmo de Thompson|imagen=noAFND.png|concepto=Algoritmo para obtener AFND-V a partir de expresiones regulares.}} | {{Definición|nombre=Algoritmo de Thompson|imagen=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 transición vacía|autómata finito no determinista con transiciones vacías]] (AFND-V) equivalente. | '''Algoritmo de Thompson'''. Algoritmo que permite a partir de una [[expresión regular]] obtener un [[autómata finito no determinista con transición vacía|autómata finito no determinista con transiciones vacías]] (AFND-V) equivalente. | ||
==Definición== | ==Definición== | ||
| − | Sea una expresión regular ''E'' se recorre la misma según el orden de precedencia operacional (*, | + | 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: |
# 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 ''x'' se representa mediante una transición [[Archivo:AFD_Transicion.gif|middle]]. |
| − | # ''' | + | # '''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. |
| − | # '''Clausura | + | # '''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>''. |
| + | # 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 ''e<sub>22</sub>=(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 ''e<sub>21</sub>=1|2|3|4|5|6|7|8|9'' y ''e<sub>221</sub>=0|1|2|3|4|5|6|7|8|9'' hasta que se hayan reducido totalmente. | ||
==Vease también== | ==Vease también== | ||
| Línea 20: | Línea 42: | ||
==Fuentes== | ==Fuentes== | ||
# Tanembaum, A. Compilers: Principles, Tecniques, and Tools. Tomo 1. ACM Press. 5ta Edición. | # Tanembaum, A. Compilers: Principles, Tecniques, and Tools. Tomo 1. ACM Press. 5ta Edición. | ||
| − | # Conferencias de la Asignatura "Compilación 1" del | + | # Conferencias de la Asignatura "Compilación 1" del Departamento de Ciencias de la Computación de la [[Universidad de Oriente]]. [[Santiago de Cuba]], [[2000]]. |
# [http://es.wikipedia.org/wiki/Autómata_finito Autómata finito en Wikipedia]. Consultado el [[25 de noviembre]] de [[2013]]. | # [http://es.wikipedia.org/wiki/Autómata_finito Autómata finito en Wikipedia]. Consultado el [[25 de noviembre]] de [[2013]]. | ||
# 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]]. | # 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]]. | ||
última versión al 15:04 20 jun 2019
| ||||||
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:
- Se coloca el estado inicial Q0:
. - Si la expresión admite la cadena vacía, Q0 se indica como un estado final:
- Cada símbolo terminal x se representa mediante una transición
. - 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. - 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). - 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. - 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
- Tanembaum, A. Compilers: Principles, Tecniques, and Tools. Tomo 1. ACM Press. 5ta Edición.
- Conferencias de la Asignatura "Compilación 1" del Departamento de Ciencias de la Computación de la Universidad de Oriente. Santiago de Cuba, 2000.
- Autómata finito en Wikipedia. Consultado el 25 de noviembre de 2013.
- 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.
- Algoritmo de Thompson en Wikipedia. Consultado el 30 de noviembre de 2013.
