Metodo del Arbol

Método del Árbol

Evander Flores (evanderex@gmail.com)

1

Contenidos
Objetivos
Alcance
Desarrollo del tema
Resumen
2

Objetivos
 Definir el método de construcción de un DFA óptimo por

medio delos métodos del árbol y de subconjuntos.
 Ejercitar la construcción de DFA partiendo de ER.

3

Alcances
 Método de Árbol
 Definición.
 Proceso
 Ejemplo
 Método de Subconjuntos

4

Método delárbol
Proceso de transformación de ER hacia un DFA óptimo

5

Método del Árbol
Partiendo de una expresión regular
 Permite la reducción de estados repetitivos.
 Produce autómatas más eficientes
Permite la eliminación de nulos
Creando un DFA óptimo.

6

Método del Árbol
Paso 1: Aumentar la ER con $
Paso 2: Crear el árbol asociado a la ER y enumerar las hojas
Paso 3: Calcular Anulable,first, last, follow (primeros,
últimos, siguientes)
Paso 4: Construir los subconjutos
Paso 5: Construir la tabla de transiciones
Paso 4: Construir el AFD.

7

Método del Árbol

Aumento de ER con $
Elsímbolo $ permite definir la finalización de la expresión
regular. Por ejemplo:
 (b*|a*)a$
 a*b(b|a*)$

 (a|(ba)*)ba*$

8

Método del Árbol

Crear el árbol asociado
ε

a

$

a|b

ab

a*

Respetandola Precedencia de operadores
9

Método del Árbol

Ejemplo
Por ejemplo la siguiente ER: L(L|D)*
1. Aumentar la expresion ER: L(L|D)*$
2. Construir el arbol de la ER y enumerar las hojas
.
.

NodoRAIZ
$
4

L

*

1
|

10

L
2

D
3

CALCULO DE ANULABLES

11

Nodo

Anulabilidad

Hoja ε

Verdadero

Hoja a

Falso

Alternativa

Anulable(C1) OR Anulable(C2)

Union

Anulable(C1) AND Anulable(C2)Cerradura Kleene

Verdadero

Cerradura Positiva

Anulable(C1)

Aparicion

Verdadero

CALCULO DE PRIMEROS/FIRST
Nodo

Primeros/First

Hoja ε

Φ

Hoja a

Número de la Hoja

Alternativa
First(C1) UFirst(C2)
Union

If Anulable(C1) then
First(C1) U First(C2)
Else
First(C1)

Cerradura Kleene
First(C1)

12

Cerradura Positiva

First(C1)

Aparicion

First(C1)

CALCULO DE ULTIMOS/LAST
Nodo
Hoja ε
Hoja a...