Algoritmo de Thompson - Historial de revisiones

Javiermartin jc: Texto reemplazado: «
» por «»

2019-06-20T20:04:08Z

Texto reemplazado: «<div align="justify">» por «»

Carlos idict en 13:07 23 dic 2013

2013-12-23T13:07:54Z

Jhonlier12017 jc.hlg: /* Ejemplo */

2013-11-30T23:33:42Z

‎Ejemplo

Jhonlier12017 jc.hlg en 23:30 30 nov 2013

2013-11-30T23:30:06Z

Jhonlier12017 jc.hlg en 22:43 30 nov 2013

2013-11-30T22:43:01Z

Jesus GT en 22:37 30 nov 2013

2013-11-30T22:37:50Z

Jhonlier12017 jc.hlg en 22:37 30 nov 2013

2013-11-30T22:37:33Z

Jhonlier12017 jc.hlg en 22:34 30 nov 2013

2013-11-30T22:34:59Z

Jhonlier12017 jc.hlg en 22:33 30 nov 2013

2013-11-30T22:33:10Z

Jhonlier12017 jc.hlg: Página creada con '{{Definición|nombre=Algoritmo de Thompson|imagen=noAFND.png|concepto=Algoritmo para obtener AFND-V a partir de expresiones regulares.}}
'''Algoritmo de Th...'

2013-11-30T21:18:24Z

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

Página nueva

{{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 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==
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]].
# Si la expresión admite la cadena vacía, ''Q0'' se indica como un estado final: [[Archivo:AF_Estado_Inicio_Final.gif|middle]]
# '''Concatenación'''. Cada símbolo terminal se representa mediante una transición [[Archivo:AFD_Transicion.gif|middle]].
# '''Clausura (*)'''.
# '''Clausura positiva (+)'''.
# '''Disjunción (|)'''.

==Vease también==
* [[Expresión regular]].
* [[Diagrama de estados]].
* [[Autómata finito no determinista con transición vacía]].

==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|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]].
# 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]].
# [http://es.wikipedia.org/wiki/Algoritmo_de_Thompson Algoritmo de Thompson en Wikipedia]. Consultado el [[30 de noviembre]] de 2013.
</div>
[[Categoría:Matemáticas]][[Categoría:Informática]]

@@ Línea 29: / Línea 29: @@
 * [[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)*'':
+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 ''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.
+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==

@@ Línea 8: / Línea 8: @@
 # 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]]
-# 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>)''.
 # '''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>''.
 ==Vease también==

@@ Línea 10: / Línea 10: @@
 # Cada símbolo terminal 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.
-# '''Concatenación (.)'''. Sea la expresión ''e<sub>1</sub>.e<sub>2</ub>'' o más sencillamente ''e<sub>1</sub>e<sub>2</ub>'' 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>''.
@@ Línea 24: / Línea 24: @@
 # 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]].
 # [http://es.wikipedia.org/wiki/Algoritmo_de_Thompson Algoritmo de Thompson en Wikipedia]. Consultado el [[30 de noviembre]] de 2013.
+</div>
 [[Categoría:Matemáticas]][[Categoría:Informática]]

@@ Línea 9: / Línea 9: @@
 # 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]].
-# '''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.
+# '''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.
 # '''Concatenación (.)'''. Sea la expresión ''e<sub>1</sub>.e<sub>2</ub>'' o más sencillamente ''e<sub>1</sub>e<sub>2</ub>'' 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>''.

@@ Línea 9: / Línea 9: @@
 # 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]].
-# '''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.
+# '''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.
-# '''Concatenación (.)'''. Sea la expresión ''e<sub>1<sub>.e<sub>2<sub>'' o simplemente ''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</ub>'' o más sencillamente ''e<sub>1</sub>e<sub>2</ub>'' 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>''.
-==Véase también==
+==Vease también==
 * [[Expresión regular]].
 * [[Diagrama de estados]].

@@ 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.}}
-<div align="justify">
 '''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.

@@ Línea 42: / Línea 42: @@
 ==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|Departamento de Ciencias de la Computación]] de la [[Universidad de Oriente]]. [[Santiago de Cuba]], [[2000]].
+# 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]].
 # 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]].