Facultad de Ingeniería

Teoría de Autómatas y
Lenguajes Formales
Conversión ER - AFN | AFD - ER
Profesor Guía: Alexander Espina-Leyton
[email protected]

Fecha: 30-09-2020 1
Contenido

2
Tabla de contenidos
● Repaso AFN
● Transformaciones
○ AFD a ER
■ Lemma Hopcroft
■ Lemma Arden
○ Método de Thompson (ER a AFN)
● Ejercicios
3
Repaso AFN
● En cada estado, pueden existir más de un
camino para el mismo símbolo e incluso
para la misma palabra vacía 𝜀.
● Al no ser determinista, el camino desde el
estado inicial q0 para una cadena 𝓌 puede
llevar a múltiples estados (finales y/o no
finales). 4
TRANSFORMACIONES

5
Transformaciones
Aunque las expresiones regulares describen
los lenguajes de manera completamente
diferente a como lo hacen los autómatas
finitos, ambas notaciones representan
exáctamente el mismo conjunto de
lenguajes, que hemos denominado
“lenguajes regulares”. 6
Transformaciones
● Todo lenguaje definido mediante un
autómata visto en clases, también se define
mediante una expresión regular.
● Todo lenguaje definido por una expresión
regular, puede definirse mediante un
autómata visto en clases.
7
Transformaciones

8
Página 77 del libro guía.
Lemma Hopcroft
● Conversión de un AFN en una expresión
regular mediante la eliminación de estados
(pág. 82).
○ Consiste de 3 principios, los cuales en conjunto
buscan eliminar estados no finales de un AFD/N,
remplazándolos por expresiones regulares.

9
 10

Facultad de Ingeniería
Lemma Hopcroft
(1) Un estado S va a ser eliminado.

Página 83 del libro guía. Prodecesores q y Sucesores p.

 11

Facultad de Ingeniería
Lemma Hopcroft
(2) (R + SU*T)*SU*
(3) R*

Página 84 del libro guía.

 12

Facultad de Ingeniería
Hopcroft - Ejemplo

Un AFN que acepta cadenas que tienen un 1 a dos o tres posiciones respecto del final.

Página 85 del libro guía.

 13

Facultad de Ingeniería
Hopcroft - Ejemplo

El autómata de la figura, con expresiones regulares como etiquetas

Página 85 del libro guía.

 14

Facultad de Ingeniería
Hopcroft - Ejemplo

Se elimina el estado no final B. El estado B tiene un predecesor A y un

sucesor C. Utilizando (1) Q1 = 1, P1=0+1, R11=∅ (ya que el arco A hasta C
no existe) y S = ∅ (porque no existe ningún bucle en estado B).
Como resultado, la expresión sobre el nuevo arco de A hasta C es:
R11 + Q1S*P1 = ∅ + 1∅*(0+1)
Observe que ∅* = 𝜀, por L(∅*) = {𝜀} ∪ L(∅) ∪ L(∅)L(∅) ∪ ...
por lo tanto ∅ + 1∅*(0+1) equivale a 1(0+1)
Página 85 del libro guía. No hay puntos finales en las últimas tres líneas. Es para no confundir.
 15

Facultad de Ingeniería
Hopcroft - Ejemplo

Autómata de dos estados con los estados A y D. Utilizando (2), R = 0+1,

S = 1(0+1)(0+1), T=∅ y U = ∅. La expresión U*, puede reemplazarse por 𝜀.
Además, la expresión SU*T es equivalente a ∅, ya que T, es ∅.
La expresión genérica (R + SU*T)*SU* se simplifica por lo tanto en este
caso a R*S o (0+1)*1(0+1)(0+1)

Página 85 del libro guía.

 16

Facultad de Ingeniería
Hopcroft - Ejemplo

Finalmente, el otro estado de aceptación que debemos tratar. Utilizando

nuevamente (2), obtenemos la expresión regular (0+1)*1(0+1)
Para obtener la expresión regular de todo el autómata, se deben unir
(+ o |) las dos expresiones de autómatas con estados finales.

(0+1)*1(0+1)+(0+1)*1(0+1)(0+1)

Página 85 del libro guía.

Lemma Arden
Este lemma, consiste en establecer un
sistema de ecuaciones con los estados de
un AFN.
Se relaciona el estado de origen, la función
de transición y los estados de destino.

17
Lemma Arden
A0= 𝒶A1∪ 𝑏A3
A1= 𝒶A5∪ 𝑏A2
A2= 𝒶A5∪ 𝑏A5∪ 𝜀
A3= 𝒶A4∪ 𝑏A5
A4= 𝒶A5∪ 𝑏A5∪ 𝜀 Regla, si qi ∈ F, 𝜀 ∈ Ai, es decir, como es
de aceptación, se añade 𝜀.
A5= 𝒶∅ ∪ 𝑏∅ = ∅
18
Lemma Arden
Debemos despejar A0 en el sistema de
ecuaciones creado.
A4= 𝒶A5∪ 𝑏A5∪ 𝜀 = 𝒶∅ ∪ 𝑏∅ ∪ 𝜀 = ∅ ∪ ∅ ∪ 𝜀 = 𝜀
A3= 𝒶A4∪ 𝑏A5 = 𝒶𝜀 ∪ 𝑏∅ = 𝒶
A2= 𝒶A5∪ 𝑏A5∪ 𝜀 = A4 = 𝜀
A1= 𝒶A5∪ 𝑏A2 = 𝒶∅ ∪ 𝑏𝜀 = 𝑏
A0= 𝒶A1∪ 𝑏A3 = 𝒶𝑏 ∪ 𝑏𝒶 Por lo tanto, L(M) = (𝒶b+b𝒶)

19
Lemma Arden
¿Qué pasa con la estrella de kleene?

20
Fuente: Página 50 del libro de "autómatas y Lenguajes Formales - Edgar Alberto Quiroga Rojas"
Lemma Arden
¿Qué pasa con la estrella de kleene?
Considere el siguiente ejemplo.
A = 1A U 0B
B = 1∅ U 0C
C = 1∅ U 0∅ U 𝜀 = 𝜀

B=0
A = 1A U 00
A = 1*00

21
Lemma Arden
¿Qué pasa con la estrella de kleene?
Considere el siguiente ejemplo.
A = 1A U 0B
B = 1∅ U 0C
C = 1∅ U 0C U 𝜀 = 0C U 𝜀 (lo forzaremos hasta el final, para
expresar el problema que acarrearía)

B = 0(0C U 𝜀)
A = 1A U 00(0C U 𝜀)
A = 1*000C U 1*00𝜀 = 1*00(0C U 𝜀) (por quiroga)

Ahora despejamos C = 0C U 𝜀 = 0*𝜀 (por quiroga)

A = 1*00(0*𝜀) 22
A = 1*000*𝜀 = 1*000* = 1*00+
Lemma Arden
Veamos el siguiente caso
A = 0A +1B + 𝜀
B = 0∅ + 1B + 𝜀
Si profundizamos un poco en la
B = 1B + 𝜀 = 1*𝜀 = 1* solución podríamos ver, que la
A = 0A + 11* + 𝜀 conversión a Estrella de Kleene, no
= 0*(11* + 𝜀) sólo afecta a 1B, sino que también a
𝜀.
= 0*11* + 0*𝜀 = 0*1+ + 0*
Vemos qué, desprendiendo de que A puede llamar a A leyendo un 0 ninguna, una o muchas veces.
A = 0A + 11* + 𝜀
A = 0(0A + 11* + 𝜀) + 11* + 𝜀
A = 0(0(0A + 11* + 𝜀) + 11* + 𝜀) + 11* + 𝜀
...
Se podría decir que A, siempre nos llevará a un estado con A, tantas veces como queramos 23
Lemma Arden
Veamos el siguiente caso
Digamos que queremos sólo tres ceros (000).
A = 0A + 11* + 𝜀
A = 0(0A + 11* + 𝜀) + 11* + 𝜀
A = 0(0(0A + 11* + 𝜀) + 11* + 𝜀) + 11* + 𝜀
Similar a una GLC, obtendremos lo siguiente.
= 0(0(0 + 11* + 𝜀) + 11* + 𝜀) + 11* + 𝜀
= 0(00 + 011* + 0𝜀 + 11* + 𝜀) + 11* + 𝜀
= 000 + 0011* + 00𝜀 + 011* + 0𝜀 + 11* + 𝜀
Cada A, contiene a A * veces, más ninguno de los otros elementos se
repite * veces.

24
Estrella de Kleene Arden
El libro de Quiroga (página 51) muestra el siguiente ejemplo:

Vale la pena mencionar, que se deben procurar ordenar el

elemento que se repetirá dejándolo al comienzo de la
ecuación, para evitar cometer errores. Como en los
ejemplos resaltados en rojo.

25
 Estrella de Kleene Arden
De lo anterior, podemos ejemplificar el siguiente caso.
A = 0A + 1A + 1B + 𝜀 = (0+1)A + 1B + 𝜀 /// Para aplicar la regla de
distributividad, es importante que la letra A esté, para ambos casos (0A y 1A), en el
mismo lado de la palabra (propiedad de concatenación).
B = 0∅ + 1B + 𝜀 = 1B + 𝜀 = 1*

A = (0+1)A + 11* + 𝜀
A = (0+1)*(11* + 𝜀)

26
 Estrella de Kleene Arden
Y como último ejemplo, consideremos el siguiente AFN.

A = 0∅ + 1B
B = (0 + 1)B + 1C + 0D + 𝜀
C = 0∅ + 1C + 𝜀 = 1*
D = 0∅ + 1B = 1B
B = (0+1)B + 11* + 01B + 𝜀
B = (0+1+01)B + 11* + 𝜀
B = (0+1+01)*11* + (0+1+01)*𝜀 = (0+1+01)*(1+ + 𝜀)
A = 1(0+1+01)*(1+ + 𝜀)

27
Método Thompson
1. La función Th, para un caso base que
cumpla.
a. Exactamente un estado de
aceptación. L = {𝜀}
b. Ningún arco que entre en el
estado inicial: L = ∅.
c. Ningún arco que salga del
estado de aceptación. L(a)
28
Página 87 del libro guía.
Método Thompson
1. Transformación ER a
AFN-𝜀 utilizando las
siguientes reglas
a. R + S (unión)
b. RS (Concatenación)
c. R*

29
Página 88 del libro guía.
 30

Facultad de Ingeniería
Thompson - Ejemplo
Deseamos convertir la expresión regular
(0 + 1)* 1(0 + 1) en un AFN-𝜀.
- Primero la parte 0+1, utilizando (a).
- A continuación (0+1)* se utiliza (c)
- Finalmente (b), para concatenar toda la
ER, como muestra la siguiente imagen.

Página 89 del libro guía. Información detallada.

 31

Facultad de Ingeniería
Thompson - Ejemplo
0+1

(0 + 1)*

Página 90 del libro guía.

 32

Facultad de Ingeniería
Thompson - Ejemplo

(0 + 1)*1(0+1)

Página 90 del libro guía.

Ejercicios

33
 34

Facultad de Ingeniería
Ejercicios
1. Para el siguiente AFN
a. Transforme el siguiente AFN a AFD
b. Utilice el Lemma Arden, para obtener la ER
desde el AFN
 35

Facultad de Ingeniería
Solución
AFN a AFD 0 1

->A A {A,B}

{A,B} {A,C} {A,B,C}

*{A,C} {A,D} {A,B,D}

*{A,B,C} {A,C,D} {A,B,C,D}

*{A,D} A {A,B}

*{A,B,D} {A,C} {A,B,C}

*{A,C,D} {A,D} {A,B,D}

*{A,B,C,D} {A,C,D} {A,B,C,D}

 36

Facultad de Ingeniería
Solución
1) S. ecuaciones 2) Debemos despejar A. Comenzaremos despejando D

A: 0A U 1A U 1B D: ∅U∅U𝜀=𝜀

B: 0C U 1C C: 0𝜀 U 1𝜀 U 𝜀 = 0 U 1 U 𝜀

C: 0D U 1D U 𝜀 B: 0(0 U 1 U 𝜀) U 1(0 U 1 U 𝜀) = (0 U 1)(0 U 1 U 𝜀)

D: 0∅ U 1∅ U 𝜀 A: 0A U 1A U 1B = (0 U 1)A U 1B = (0 U 1)*1(0 U 1)(0 U 1 U 𝜀)

(0+1)*1(0+1)((0+1)+𝜀)
 37

Facultad de Ingeniería
Ejercicios
1. Transforme el siguiente AFD a ER
 38

Facultad de Ingeniería
Solución
1) S. ecuaciones 2) Debemos despejar A. Comenzaremos despejando D

A: 1A U 0B B: 0*(1A U 𝜀) = 0*1A U 0*

B: 0B U 1A U 𝜀 A: 1A U 0(0*1A U 0*) = 1A U 00*1A U 00* = (1 U 00*1)A U 00*

Finalmente a (1 U 00*1)A U 00* le aplicamos la regla de Kleene

aprendida de Quiroga, obteniendo:

ER: (1 + 00*1)*00*
 39

Facultad de Ingeniería
Ejercicios
1. He aquí una tabla de transiciones para un AFD:
a. Convierta el siguiente AFD en
una expresión regular
utilizando el Lemma de
Arden
 40

Facultad de Ingeniería
Solución - AFD diagrama
 41

Facultad de Ingeniería
Solución - Transformación
Qs Ecuaciones

p: 1p + 0s + 𝜀 1*(0s + 𝜀) 1*0s + 1*𝜀 (1*0(10*1+0)(110*1 + 10)*0)*1*

q: 1s + 0p 1(10*1q + 0q) + 0p (110*1 + 10)q + 0p (110*1 + 10)*0p

r: 0r + 1q 0*(1q) 0*1q 0*1(110*1 + 10)*0p

s: 1r + 0q 1(0*1q) + 0q 10*1q + 0q (10*1+0)(110*1 + 10)*0p

En la siguiente tabla explicaré el orden que seguí para resolver la ecuación:

p: 1p + 0s + 𝜀 1ero kleene p 4to álgebra de ER 7mo reemplazo s y kleene p

q: 1s + 0p 3ro reemplazo s 4to álgebra de ER 5to (kleene) sobre q

r: 0r + 1q 1ero kleene sobre r 4to álgebra de ER 6to reemplazo q

s: 1r + 0q 2do reemplazo r 4to álgebra de ER 6to reemplazo q

 42

Facultad de Ingeniería
Ejercicios
1. Convierta las siguientes expresiones regulares en
un AFN-𝜀.
a. 01*
b. (0+1)01
c. 00(0+1)*
43

Facultad de Ingeniería
Solución A
44

Facultad de Ingeniería
Solución B
45

Facultad de Ingeniería
Solución C
Anexos

46
 47

Facultad de Ingeniería
Fuentes
➢ Ponencias Curso Carlos Rey Barra
➢ Ponencias Curso Carlos Gómez-Pantoja
➢ J. Hopcroft, R. Motwani, J. Ullman. (2001).
Introduction to Automata Theory, Languages,
and Computation. Pearson Education.
 48

Facultad de Ingeniería
Ejercicio T Parte 1
Eliminando 2, llegamos a lo siguiente.
Eliminar el 2 se hace sencillo, sólo
porque es un nodo intermedio a 3 y 4.
Así que es llegar de 1->2 y desde ahí
a 3 y 4.
 49

Facultad de Ingeniería
Ejercicio T Parte 2
Primero asumamos el llegar a 3 como estado
final (eliminando 4) y luego es homólogo llegar
a 4 como estado final. Y ambos se deben unir.

1⇒3 = (0+11(00)*1)*(10(00)*)
1⇒4 = (0+10(00)*1)*(11(1+00(00)*1)*)
4⇒3 = (1+00(00)*1)*0
En el 1⇒3, me pregunto ¿Cómo llego
del 1 al 3, sin pasar por el 4?.
3⇒4 = (0(00)*11*0)*((0(00)*1)1*)
(0+11(00)*1) Representa el volver al 1. 3⇒1 = (10*10(00)*)*(10*)
(caso (2) hopcroft)

(1⇒3 + 1⇒4∙4⇒3)
Luego, como busco llegar desde 1, hasta 3
y todos los caminos intermedios (y ciclos ∙(
por formar). Se genera una unión, como el (3⇒4∙4⇒3)
caso (1) hopcroft. Ojo que en 1, ya están + (3⇒1∙
consideradas las formas que te devuelven a
1. Y luego le concateno los ciclos desde 3 + (1⇒3+ 1⇒4∙4⇒3)
a 3. + )*
 Facultad de Ingeniería

Teoría de Autómatas y
Lenguajes Formales
Conversión ER - AFN | AFD - ER
Profesor Guía: Alexander Espina-Leyton
[email protected]

Fecha: 02-10-2019 50