circuitos

Compiladores e Interpretes

EPCI - UNPRG

DIAGRAMAS DE TRANSICIONES
Son grafos dirigidos que especifican el reconocimiento de un token como elemento del lenguaje.
En un diagrama de transición (DT) se compila un token.
Partes:
inicio

Estado inicial
Estado

n

Estado final

0

n

Transición

0

1
id

Arista

Se dice que un token se compila en un DT, si este esreconocido o cumple una ruta desde el estado
inicial hasta un estado de aceptación (estado final).
DT básicos:
a

-

ER: a | b

inicio

0

L (a | b) = L(a) | L(b) = {a,b}

-

ER: ab
inicioL (ab) = L(a) L(b) = {ab}

-

a

0

b

1

2

a

ER: a*
L (a*) = L(a)* = {Є, a, aa, aaa, aaaa, ...}

-

1

b

inicio

0

Є

1

ER: a+

a

L (a+ ) = L(a)+ = {a,aa, aaa, aaaa, ...}

inicio

0

a

1

a

a+  aa*

Ing. Luis Reyes Lescano

inicio

0

a

1

Є

2

a*

1

Compiladores e Interpretes

EPCI - UNPRG

EJERCICIOS
I.Desarrollar los Diagramas de Transición (DT) de las siguientes Expresiones Regulares
(ER).
1. (a | b) a*bb
sobre ={a,b}
2. (a* | b+)* a* | b* sobre ={a, b}
Є
a
inicio

Є

0

a

0Є

1

a
inicio

a
Є

2

Є

5

6

b
Є

1

b

2

b

b

b

3

Є

4
3

b

Є

Є

Є
4

3. ((xy* | mn*)* | xy)+ | mn

sobre

={xy, mn}

Є

Є

Є

xy2

Є
inicio

0

Є

xy

Є

1
Є

Є

2

Є

mn

Є

4

Є

mn

1
Є

3

Є

4

Є

4

3

Є

Є

xy

xy
Є
mn

4. ((0* | 1)+ | 0* | 1+)* (0 | 1*)*sobre

={0,1}

Є
Є

Є
0

0

1

3

6

11

Є

Є
inicio

0

Є

1

1

Є

Є
2

Є

1

4

Є
0

1

7

5

Є

9

0

10

Є

Є

Є
1

Є

Є

Є8
Є

Ing. Luis Reyes Lescano

2

Compiladores e Interpretes

II.

EPCI - UNPRG

Desarrollar los Diagramas de Transición (DT) de las siguientes Definicione s Regulares
(DR).
1....