Metodo De Thompson
Páginas: 6 (1300 palabras)
Publicado: 21 de octubre de 2011
Método de Thompson
Lenguajes Formales y de Programacion
Objetivos
Definir el proceso del Algoritmo de Construcción de Thompson a partir de una ER Construir a partir de AFN un AFD equivalente por el cálculo de la cerradura
Alcances
Método de Construcción de AFN de Thompson.
Kenneth Lane Thompson. Nomenclatura
Transformación de AFN – AFD
Cálculo de la Cerradura Proceso deTransformación
Algoritmo de Construcción Thompson
Kenneth Lane Thompson, Nomenclatura,
Algoritmo de Construcción de Thompson
En honor a Kenneth Lane Thompson, pionero en el desarrollo de sistemas operativos y procesadores. Diseñador y colaborador del Sistema Operativo Unix , Lenguaje Bon, B, C.
Algoritmo de Construcción de Thompson
El algoritmo construye a partir de expresiones regulares undiagrama de AFN, para luego poder generar un AFD mínimo equivalente. Utiliza una notación estándar para generar un AFN
Nomenclatura de Thompson
Para la representación de una cadena vacía se utiliza el símbolo ε.
Φ
Cadena Vacía
Nomenclatura de Thompson
Para representar un símbolo, se utilizan dos estados y una transición para el movimiento con el símbolo.
r
Nomenclatura deThompson
Para la concatenación de dos símbolos es necesario únicamente se unen cada uno de los símbolos por
rs
Concatenación de símbolo
10
25/10/2010
Nomenclatura de Thompson
Para la elección de alternativas, crear transiciones ε para la unión de las transiciones.
r|s
Elección de alternativas
11 25/10/2010
Nomenclatura de Thompson
Para la cerradura Positiva, se agregantransiciones ε para retornar al estado previo, permitiendo agregar 1 o mas veces el símbolo
r+
Cerradura de Kleene
12 25/10/2010
Nomenclatura de Thompson
Para la cerradura de Kleene, se agregan transiciones ε para retornar a estado previo.Y otra transición ε para saltar la transición con r.
r*
Cerradura de Kleene
25/10/2010 13
Ejemplo Método de Thompson
Diagrama del AFN querepresenta la ER a*b. 1. Parte de la cerradura de Kleene. a*b
14
25/10/2010
Ejemplo Método de Thompson
2. Para continuar se generan la concatenación del símbolo b a*b
25/10/2010
15
Ejemplo Método de Thompson
3. Para finalizar se numeran los estados y se indica el estado inicial y final a*b
16
25/10/2010
Ejemplo Método de Thompson
A partir de la ER (b|(b*a)*)a 1.Parte de la cerradura de Kleene que se encuentra dentro de paréntesis. (b|(b*a)*)a
25/10/2010
17
Ejemplo Método de Thompson
A partir de la ER (b|(b*a)*)a 2. Completamos dicho paréntesis concatenando el símbolo a (b|(b*a)*)a
25/10/2010
18
Ejemplo Método de Thompson
A partir de la ER (b|(b*a)*)a 3. Aplicar la Cerradura de Kleene al paréntesis (b|(b*a)*)a
ε
ε
25/10/201019
Ejemplo Método de Thompson
A partir de la ER (b|(b*a)*)a 4. La elección de alternativas del b y el diagrama anterior. ε (b|(b*a)*)a
ε
25/10/2010
20
Ejemplo Método de Thompson
5. Concatenamos el último símbolo, enumerando e indicando el estado inicial y el final ε (b|(b*a)*)a
ε
25/10/2010
21
Conversión AFN - AFD
Cálculo de la Cerradura
22
25/10/2010 Cálculo de la Cerradura
Parte de la unión de conjunto de estados pertenecientes al AFN, que se representara por un único estado en el AFD. Donde existe un camino etiquetado que conduce del estado de inicio al de aceptación.
23
25/10/2010
Operaciones de Cerradura
Clausura (Sn): conjunto de estados del AFN alcanzables desde el estado Sn, con transiciones ε (épsilon)
Por ejemplo desde q0 sepuede alcanzar q1, q2, q4.
Operaciones de Cerradura
Mov(T,a): representa el movimiento desde el estado T, con una transición a, que es parte del alfabeto. La transición Mov(q2,a) logra llegar al estado q3
Operaciones de Cerradura
Es importante llevar el control de las cerraduras que se crean, llevar el control de su uso e identificarlas cuando se haya finalizado el análisis. Además...
Lenguajes Formales y de Programacion
Objetivos
Definir el proceso del Algoritmo de Construcción de Thompson a partir de una ER Construir a partir de AFN un AFD equivalente por el cálculo de la cerradura
Alcances
Método de Construcción de AFN de Thompson.
Kenneth Lane Thompson. Nomenclatura
Transformación de AFN – AFD
Cálculo de la Cerradura Proceso deTransformación
Algoritmo de Construcción Thompson
Kenneth Lane Thompson, Nomenclatura,
Algoritmo de Construcción de Thompson
En honor a Kenneth Lane Thompson, pionero en el desarrollo de sistemas operativos y procesadores. Diseñador y colaborador del Sistema Operativo Unix , Lenguaje Bon, B, C.
Algoritmo de Construcción de Thompson
El algoritmo construye a partir de expresiones regulares undiagrama de AFN, para luego poder generar un AFD mínimo equivalente. Utiliza una notación estándar para generar un AFN
Nomenclatura de Thompson
Para la representación de una cadena vacía se utiliza el símbolo ε.
Φ
Cadena Vacía
Nomenclatura de Thompson
Para representar un símbolo, se utilizan dos estados y una transición para el movimiento con el símbolo.
r
Nomenclatura deThompson
Para la concatenación de dos símbolos es necesario únicamente se unen cada uno de los símbolos por
rs
Concatenación de símbolo
10
25/10/2010
Nomenclatura de Thompson
Para la elección de alternativas, crear transiciones ε para la unión de las transiciones.
r|s
Elección de alternativas
11 25/10/2010
Nomenclatura de Thompson
Para la cerradura Positiva, se agregantransiciones ε para retornar al estado previo, permitiendo agregar 1 o mas veces el símbolo
r+
Cerradura de Kleene
12 25/10/2010
Nomenclatura de Thompson
Para la cerradura de Kleene, se agregan transiciones ε para retornar a estado previo.Y otra transición ε para saltar la transición con r.
r*
Cerradura de Kleene
25/10/2010 13
Ejemplo Método de Thompson
Diagrama del AFN querepresenta la ER a*b. 1. Parte de la cerradura de Kleene. a*b
14
25/10/2010
Ejemplo Método de Thompson
2. Para continuar se generan la concatenación del símbolo b a*b
25/10/2010
15
Ejemplo Método de Thompson
3. Para finalizar se numeran los estados y se indica el estado inicial y final a*b
16
25/10/2010
Ejemplo Método de Thompson
A partir de la ER (b|(b*a)*)a 1.Parte de la cerradura de Kleene que se encuentra dentro de paréntesis. (b|(b*a)*)a
25/10/2010
17
Ejemplo Método de Thompson
A partir de la ER (b|(b*a)*)a 2. Completamos dicho paréntesis concatenando el símbolo a (b|(b*a)*)a
25/10/2010
18
Ejemplo Método de Thompson
A partir de la ER (b|(b*a)*)a 3. Aplicar la Cerradura de Kleene al paréntesis (b|(b*a)*)a
ε
ε
25/10/201019
Ejemplo Método de Thompson
A partir de la ER (b|(b*a)*)a 4. La elección de alternativas del b y el diagrama anterior. ε (b|(b*a)*)a
ε
25/10/2010
20
Ejemplo Método de Thompson
5. Concatenamos el último símbolo, enumerando e indicando el estado inicial y el final ε (b|(b*a)*)a
ε
25/10/2010
21
Conversión AFN - AFD
Cálculo de la Cerradura
22
25/10/2010 Cálculo de la Cerradura
Parte de la unión de conjunto de estados pertenecientes al AFN, que se representara por un único estado en el AFD. Donde existe un camino etiquetado que conduce del estado de inicio al de aceptación.
23
25/10/2010
Operaciones de Cerradura
Clausura (Sn): conjunto de estados del AFN alcanzables desde el estado Sn, con transiciones ε (épsilon)
Por ejemplo desde q0 sepuede alcanzar q1, q2, q4.
Operaciones de Cerradura
Mov(T,a): representa el movimiento desde el estado T, con una transición a, que es parte del alfabeto. La transición Mov(q2,a) logra llegar al estado q3
Operaciones de Cerradura
Es importante llevar el control de las cerraduras que se crean, llevar el control de su uso e identificarlas cuando se haya finalizado el análisis. Además...
Leer documento completo
Regístrate para leer el documento completo.