UNIVERSIDAD DE TARAPACÁ
FACULTAD DE INGENIERÍA
Departamento de Ingeniería en Computación e Informática
Taller Evaluado 2
Autor(es): Vranika Santiago Yovich
Gabriel Pailamilla Perez
Luciano Vera Norambuena
Bastián Vega Devia
Curso: Teoría de la Computación (Grupo A)
Profesor: Dr. Raúl Herrera Acuña
ARICA, 18 DE ABRIL, 2024
Teoría de la Computación Taller 1
Tabla de Contenidos
1. INTRODUCCIÓN ....................................................................................................... 3
2. ALFABETOS Y LENGUAJES ........................................................................................ 5
2.1. Alfabetos, palabras y lenguajes ....................................................................................... 5
2.1.1. Ejercicio 1.1.2................................................................................................................................... 5
2.2. Operaciones con cadenas ................................................................................................ 6
2.2.1. Ejercicio 1.2.5................................................................................................................................... 6
2.2.2. Ejercicio 1.2.6................................................................................................................................... 6
2.3. Operaciones con lenguajes .............................................................................................. 7
2.3.1. Ejercicio 1.3.1................................................................................................................................... 7
2.3.2. Ejercicio 1.3.3................................................................................................................................... 7
2.3.3. Ejercicio 1.3.5................................................................................................................................... 7
2.3.4. Ejercicio 1.3.7................................................................................................................................... 8
2.3.5. Ejercicio 1.3.12 ................................................................................................................................ 9
2.3.6. Ejercicio 1.3.17 .............................................................................................................................. 10
3. LENGUAJES REGULARES ......................................................................................... 11
3.1. Lenguajes sobre alfabetos ............................................................................................. 11
3.1.1. Ejercicio 2.1.2................................................................................................................................. 11
3.2. Lenguajes y expresiones regulares ................................................................................. 12
3.2.1. Ejercicio 2.2.2................................................................................................................................. 12
3.2.2. Ejercicio 2.2.8................................................................................................................................. 13
3.3. Autómata finito determinista ........................................................................................ 14
3.3.1. Ejercicio 2.3.3................................................................................................................................. 14
3.4. AFD y lenguajes ............................................................................................................ 16
3.4.1. Ejercicio 2.4.2................................................................................................................................. 16
3.5. Autómata finito no determinista ................................................................................... 18
3.5.1. Ejercicio 2.5.4................................................................................................................................. 18
3.6. Equivalencia de AFN y AFD ............................................................................................ 19
3.6.1. Ejercicio 2.6.1................................................................................................................................. 19
3.7. Transiciones.................................................................................................................. 21
3.7.1. Ejercicio 2.7.5................................................................................................................................. 21
3.8. Autómatas finitos y expresiones regulares ..................................................................... 23
3.8.1. Ejercicio 2.8.13 .............................................................................................................................. 23
3.9. Propiedades de los lenguajes regulares ......................................................................... 24
3.9.1. Ejercicio 2.9.2................................................................................................................................. 24
REFERENCIAS ................................................................................................................... 25
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 2
Teoría de la Computación Taller 1
Índice de Tablas
Tabla 1 Ejercicio 2.3.3 ..................................................................................................... 14
Tabla 2 Ejercicio 2.6.1 ..................................................................................................... 18
Tabla 3 Diagrama de transición ...................................................................................... 19
Tabla 4 Diagrama de conversión .................................................................................... 19
Tabla 5 Transición Ejercicio 2.7.5 ................................................................................... 21
Tabla 6 Autómatas finitos y expresiones regulares........................................................ 23
Índice de Figuras
Ilustración 1 Diagrama de transición de estados – Ejercicio 2.3.3 ................................. 14
Ilustración 2 Ejercicio 2.4.2 letra a. ................................................................................ 16
Ilustración 3 Ejercicio 2.4.2 letra b. ................................................................................ 16
Ilustración 4 Ejercicio 2.4.2 letra c. ................................................................................. 16
Ilustración 5 Ejercicio 2.4.2 letra d. ................................................................................ 17
Ilustración 6 Ejercicio 2.4.2 letra e. ................................................................................ 17
Ilustración 7 Diagrama de Transición - Ejercicio 2.5.4 ................................................... 18
Ilustración 8 Enunciado ejercicio 2.6.1 ........................................................................... 19
Ilustración 9 AFD – Ejercicio 2.6.1. ................................................................................. 20
Ilustración 10 Transiciones – Ejercicio 2.7.5 ................................................................... 21
Ilustración 11 Ejercicio autómatas finitos y expresiones regulares – Ejercicio 2.8.13 ... 23
Ilustración 12 Enunciado ejercicio 2.9.2 ......................................................................... 24
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 3
Teoría de la Computación Taller 1
1. INTRODUCCIÓN
En este taller, se mostrarán los ejercicios resueltos correspondientes a los capítulos 1 y
2, del libro de Teoría de autómatas y lenguajes formales. Abordando los siguientes
temas a tratar:
• Alfabetos y lenguajes
o Palabras
o Operaciones con cadenas
o Operaciones con lenguajes
• Lenguajes Regulares
o Lenguaje sobre alfabetos
o Expresiones regulares
o Autómata finito determinista y no determinista
o ε- Transiciones
o Propiedades lenguaje regular
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 4
Teoría de la Computación Taller 1
2. ALFABETOS Y LENGUAJES
2.1. Alfabetos, palabras y lenguajes
2.1.1. Ejercicio 1.1.2
¿Por qué el lenguaje vacío ∅ no es el mismo que {ε}?
Por un lado, ∅ es un lenguaje vacío, es decir, no se encuentra compuesto de ninguna
cadena (o elementos), por lo que, su cardinalidad es 0.
Por otro lado, {ε} es un lenguaje formado por la palabra vacía, es decir, tiene un
elemento que es Ɛ, por lo que, su cardinalidad es 1.
∴ ∅ no es lo mismo que {ε}.
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 5
Teoría de la Computación Taller 1
2.2. Operaciones con cadenas
2.2.1. Ejercicio 1.2.5
Obtener todos los prefijos, sufijos y subpalabras de la palabra w = “bar” sobre el alfabeto
inglés.
Los prefijos de w son {ε, b, ba, bar}
Los sufijos de w son {ε, r, ar, bar}
Las subpalabras de w son {ε, b, a, r, ba, ar, bar}
2.2.2. Ejercicio 1.2.6
Probar formalmente que (wy)' = y' w'.
(wy)’ = y’ w’ /Aplicando inversa
((wy)’)’ = (y’w’)’ /Aplicando la propiedad (x’)’ = x
wy = (w’)’ (y’)’ /Aplicando la propiedad (x’)’ = x
wy = wy
∴ Se demuestra que (wy)' = y' w'.
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 6
Teoría de la Computación Taller 1
2.3. Operaciones con lenguajes
2.3.1. Ejercicio 1.3.1
Para todo lenguaje A, ¿Qué es 𝐴 ∙ ∅ ?
La definición de lenguaje concatenación de A y B está dada por:
𝐴 ∙ 𝐵 {𝑤 ∙ 𝑥 | 𝑤 𝜖 𝐴 ∧ 𝑥 𝜖 𝐵}
Donde:
𝐴 ∙ ∅ {𝑤 ∙ 𝑥 | 𝑤 𝜖 𝐴 ∧ 𝑥 𝜖 ∅ }
Dado que ∅ no contiene ninguna cadena, entonces x ∉ ∅ y por consecuencia 𝐴 ∙ ∅ = ∅.
2.3.2. Ejercicio 1.3.3
Se supone que A = {ϵ, a}. Obtener 𝐴𝑛 para n = 0, 1,2, 3. ¿Cuántos elementos tiene 𝐴𝑛
para un n arbitrario? ¿Cuáles son las cadenas de A" para un n arbitrario?
{𝜀}, 𝑠𝑖 𝑛 = 0
𝐴𝑛 = { 𝑛−1
𝐴∙ 𝐴 , 𝑠𝑖 𝑛 ≥ 1
𝐴0 = {𝜀} ; 𝑑𝑜𝑛𝑑𝑒 |𝐴0 | = 1
𝐴1 = 𝐴 ∙ 𝐴0 = {𝜀, 𝑎} ∙ {𝜀} = {𝜀, 𝑎} ; 𝑑𝑜𝑛𝑑𝑒 |𝐴1 | = 2
2 1
𝐴 = 𝐴 ∙ 𝐴 = {𝜀, 𝑎} ∙ {𝜀, 𝑎} = {𝜀, 𝑎, 𝑎𝑎} ; 𝑑𝑜𝑛𝑑𝑒 |𝐴2 | = 3
3 2
𝐴 = 𝐴 ∙ 𝐴 = {𝜀, 𝑎} ∙ {𝜀, 𝑎, 𝑎𝑎} = {𝜀, 𝑎, 𝑎𝑎, 𝑎𝑎𝑎} ; 𝑑𝑜𝑛𝑑𝑒 |𝐴3 | = 4
𝐴𝑛 = 𝐴 ∙ 𝐴𝑛−1 = {𝜀, 𝑎} ∙ {𝜀, 𝑎, 𝑎𝑎, 𝑎𝑎𝑎, … 𝑎 𝑛 } = {𝜀, 𝑎, 𝑎𝑎, 𝑎𝑎𝑎, … 𝑎 𝑛 } ; 𝑑𝑜𝑛𝑑𝑒 |𝐴𝑛 | = 𝑛 + 1
∴ 𝐴𝑛 para un n arbitrario tendrá n + 1 elementos. Además, las cadenas serán
{𝜀, 𝑎, 𝑎𝑎, 𝑎𝑎𝑎, … 𝑎𝑛 } .
2.3.3. Ejercicio 1.3.5
Sean A = {ϵ, ab} y B = {cd}. ¿Cuántas cadenas hay en 𝐴𝑛 𝐵 para un n arbitrario?
𝐴0 = {𝜀 }
𝐴1 = 𝐴 · 𝐴0 = {𝜀, 𝑎𝑏} ∙ {𝜀} = {𝜀, 𝑎𝑏}
𝐴2 = 𝐴 · 𝐴1 = {𝜀, 𝑎𝑏} ∙ {𝜀, 𝑎𝑏} = {𝜀, 𝑎𝑏, 𝑎𝑏𝑎𝑏}
𝐴3 = 𝐴 · 𝐴2 = {𝜀, 𝑎𝑏} ∙ {𝜀, 𝑎𝑏, 𝑎𝑏𝑎𝑏} = {𝜀, 𝑎𝑏, 𝑎𝑏𝑎𝑏, 𝑎𝑏𝑎𝑏𝑎𝑏}
𝐴𝑛 = 𝐴 · 𝐴𝑛−1 = {𝜀, 𝑎𝑏} ∙ {𝜀, 𝑎𝑏, 𝑎𝑏𝑎𝑏, 𝑎𝑏𝑎𝑏𝑎𝑏, … , (𝑎𝑏)𝑛 }
= {𝜀, 𝑎𝑏, 𝑎𝑏𝑎𝑏, 𝑎𝑏𝑎𝑏𝑎𝑏, … , (𝑎𝑏)𝑛 }
Para 𝐴𝑛 𝐵:
𝐴𝑛 = {𝜀, 𝑎𝑏, 𝑎𝑏𝑎𝑏, 𝑎𝑏𝑎𝑏𝑎𝑏, … , (𝑎𝑏)𝑛 }{𝑐𝑑}
= {𝑐𝑑, 𝑎𝑏𝑐𝑑, 𝑎𝑏𝑎𝑏𝑐𝑑, 𝑎𝑏𝑎𝑏𝑎𝑏𝑐𝑑, … , (𝑎𝑏)𝑛 𝑐𝑑}
∴ Las cadenas de 𝐴𝑛 serán {𝑐𝑑, 𝑎𝑏𝑐𝑑, 𝑎𝑏𝑎𝑏𝑐𝑑, 𝑎𝑏𝑎𝑏𝑎𝑏𝑐𝑑, … , (𝑎𝑏)𝑛 𝑐𝑑} para un n
arbitrario.
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 7
Teoría de la Computación Taller 1
2.3.4. Ejercicio 1.3.7
Sean A = {𝜀}, B = [aa, ab, bb), C = {𝜀, 𝑎𝑎, 𝑎𝑏} y D = ∅ el lenguaje vacío. Obtener A∪B,
A∪C, A∪D, B∪D y A∩B, B∩C, C∩D, A∩D. Suponer que F es un lenguaje cualquiera.
Obtener F∪D y F∩D.
𝐴 ∪ 𝐵 = {ϵ, aa, ab, bb}
𝐴 ∪ 𝐶 = {ϵ, aa, ab}
𝐴 ∪ 𝐷 = {ϵ}
𝐵 ∪ 𝐷 = {aa, ab, bb}
𝐴∩𝐵 =∅
𝐵 ∩ 𝐶 = {aa, ab}
𝐶∩𝐷 =∅
𝐴∩𝐷 =∅
Por último, suponiendo que F es un lenguaje cualquiera:
𝐹 ∪ 𝐷 = F, dado a que:
𝐹 ∪ ∅ = { 𝑥 | 𝑥 ∈ 𝐹 𝑜𝑟 𝑥 ∈ ∅}
=𝐹
𝐹 ∩ 𝐷 = ∅, dado que:
𝐹 ∩ ∅ = { 𝑥 | 𝑥 ∈ 𝐹 𝑎𝑛𝑑 𝑥 ∈ ∅}
=∅
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 8
Teoría de la Computación Taller 1
2.3.5. Ejercicio 1.3.12
Probar que {ϵ}∗ = {𝜀} = {ϵ}+.
Para demostrar que {ϵ}∗ = {𝜀}, se define que A = {𝜀}. Luego, al aplicar la Cerradura de
Kleene:
∞
𝐴 = ⋃ 𝐴𝑛 = 𝐴0 ∪ 𝐴1 ∪ 𝐴2 ∪ … ∪ 𝐴 𝑛
∗
𝑛=0
Se obtiene lo siguiente:
𝐴0 = {𝜀}
𝐴1 = 𝐴 ∙ {𝜀} = {𝜀} ∙ {𝜀} = {𝜀}
𝐴2 = 𝐴 ∙ {𝜀} = {𝜀} ∙ {𝜀} = {𝜀}
𝐴𝑛 = 𝐴 ∙ {𝜀 } = {𝜀 } ∙ {𝜀 } = {𝜀 }
Entonces:
𝐴𝑛 = 𝐴0 ∪ 𝐴 1 ∪ 𝐴2 ∪ … ∪ 𝐴 𝑛
= {𝜀} ∪ {𝜀} ∪ {𝜀} … ∪ {𝜀}
∴ {ϵ}∗ = {𝜀}
Ahora, para demostrar que {𝜀}+= {𝜀}, se mantiene la definición de A = {𝜀}. Luego, al
aplicar la Cerradura Positiva:
∞
𝐴 = ⋃ 𝐴𝑛 = 𝐴1 ∪ 𝐴2 ∪ … ∪ 𝐴 𝑛
+
𝑛=1
Se obtiene lo siguiente:
𝐴1 = 𝐴 ∙ {𝜀} = {𝜀} ∙ {𝜀} = {𝜀}
𝐴2 = 𝐴 ∙ {𝜀} = {𝜀} ∙ {𝜀} = {𝜀}
𝐴𝑛 = 𝐴 ∙ {𝜀} = {𝜀} ∙ {𝜀} = {𝜀}
Entonces:
𝐴𝑛 = 𝐴 1 ∪ 𝐴2 ∪ … ∪ 𝐴 𝑛
= {𝜀} ∪ {𝜀} … ∪ {𝜀}
∴ {ϵ}+ = {𝜀}
∴ {ϵ}∗ = {𝜀} = {ϵ}+
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 9
Teoría de la Computación Taller 1
2.3.6. Ejercicio 1.3.17
Probar que {𝐴∗ }∗ = 𝐴∗ , (𝐴∗ )+ = 𝐴∗ y (𝐴+ )∗ = 𝐴∗
1. (𝑨∗ )∗ = 𝑨∗
Por la Cerradura de Kleene:
∞
(𝐴∗ )∗ = ⋃(𝐴∗ )𝑛 = (𝐴∗ )0 ∪ (𝐴∗ )1 ∪ (𝐴∗ )2 … ∪ (𝐴∗ )𝑛
𝑛=0
Se obtiene que:
(𝐴∗ )∗ = (𝐴∗ )0 ∪ (𝐴∗ )1 ∪ (𝐴∗ )2 ∪ … ∪ (𝐴∗ )n
= {𝜀} ∪ A∗ ∪ A∗ ∪ … ∪ A∗
= A∗
∴ (𝐴∗ )∗ = 𝐴∗
2. (𝑨∗ )+ = 𝑨∗
Por la Cerradura Positiva:
∞
(𝐴∗ )+ = ⋃(𝐴∗ )𝑛 = (𝐴∗ )0 ∪ (𝐴∗ )1 ∪ (𝐴∗ )2 … ∪ (𝐴∗ )𝑛
𝑛=0
Se obtiene que:
{A∗ }+= (A∗ )1 ∪ (A∗ )2 ∪ (A∗ )3 ∪ … ∪ (𝐴∗ )n
= A∗ ∪ A∗ ∪ A∗ ∪ …
= A∗
∴ (𝐴∗ )+ = 𝐴∗
3. (𝑨+ )∗ = 𝑨∗
{A+ }∗ = (A+ )0 ∪ (A+ )1 ∪ (A+ )2 ∪ … ∪ (A+ )n
= {ϵ} ∪ A+ ∪ A+ ∪ A+ ∪ … ∪ A+ / Como {𝜀 } ∪ A+ = 𝐴∗
= A∗
∴ (𝐴+ )∗ = 𝐴∗
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 10
Teoría de la Computación Taller 1
3. LENGUAJES REGULARES
3.1. Lenguajes sobre alfabetos
3.1.1. Ejercicio 2.1.2
En el caso general de que haya n caracteres en el alfabeto Σ ¿cuántas palabras de
longitud k habrá? Si ordenamos las palabras de Σ en orden lexicográfico y les asignamos
números comenzando por el 0 para Ɛ ¿Cuál será el número asignado a la última palabra
de longitud k?
El número de palabras que tendrán la longitud de K se define como 𝑛 𝐾 , donde n es la
cantidad de caracteres que contiene el alfabeto y K es la longitud de la palabra. Por otro
lado, el numero asignado a la ultima palabra de longitud K estaría dado por la siguiente
Teoría de la Computación Taller 1
formula:
𝑖=𝑘
K = Longitud
N = Caracteres 𝑛𝑖
Σ = Alfabeto 𝑖=0
Como se organizó de manera lexicográfica se le restaría 1, ya que empieza a contar
desde 0.
𝑖=𝑘
( 𝑛𝑖 ) − 1
𝑖=0
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 11
Teoría de la Computación Taller 1
3.2. Lenguajes y expresiones regulares
3.2.1. Ejercicio 2.2.2
Verificar que el lenguaje de todas las cadenas de unos y ceros que tienen al
menos dos ceros consecutivos, es un lenguaje regular.
Se tienen los lenguajes regulares A = {0} y B = {1}. Usando estos lenguajes se puede
construir el lenguaje de todas las cadenas de unos y ceros que tienen al menos dos ceros
consecutivos, ya que, podemos utilizar los operadores de unión (∪), concatenación (⋅) y
estrella de Kleene (∗) para construir cadenas más complejas a partir de A y B.
i. Construcción del alfabeto {0, 1}.
Con la operación (𝐴 ∪ 𝐵) = {0,1} se forma el alfabeto de ceros y unos.
ii. Formar la expresión
La expresión (𝑨 ∪ 𝑩) ∗ genera todas las combinaciones posibles de ceros y unos,
incluyendo la cadena vacía.
⇒ ({𝟎} ∪ {𝟏}) ∗ es equivalente a (𝑨 + 𝑩) ∗
Luego, para asegurar la aparición de dos ceros consecutivos al menos una vez,
podemos concatenar A y A para formar “00”.
⇒ ({0} ⋅ {0}) es equivalente a {00}
La expresión completa estaría dada por:
(A ∪ B)*(AA)(A ∪ B)* = ({0} ∪ {1})*({0}{0})({0} ∪ {1})*
Sabemos que A y B son lenguajes regulares, por lo que tanto las operaciones de
concatenación, unión y cerraduras aplicadas en estos generan lenguajes regulares, por
lo que sí es un lenguaje regular.
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 12
Teoría de la Computación Taller 1
3.2.2. Ejercicio 2.2.8
Probar que (aa)*a = a(aa)*
Si 𝑤 𝜖 (aa)*a entonces:
w = (𝑎0 𝑎0 )(𝑎1 𝑎1 )(𝑎2𝑎2 ). . . (𝑎𝑛 𝑎𝑛 )𝑎, para algún 𝑛 ≥ 0.
Dado a que la concatenación es asociativa, al re-asociar la expresión anterior nos queda:
w = 𝑎0 (𝑎0 𝑎1 )(𝑎1 𝑎2 ). . . (𝑎𝑛 𝑎) = a(aa)*
∴ (aa)*a = a(aa)*
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 13
Teoría de la Computación Taller 1
3.3. Autómata finito determinista
3.3.1. Ejercicio 2.3.3
Sea M = {𝑄, ∑, 𝑠, 𝐹, 𝛿} dado por:
Q = {q0, q1, q2, q3}
Σ = {0, 1}
F = {q0}
s = q0
y δ dada por la tabla
σ 0 1
q0 q2 q1
q1 q3 q0
q2 q0 q3
q3 q1 q2
Tabla 1 Ejercicio 2.3.3
Construir el diagrama de transición. Obtener la secuencia de estados por los que se pasa
para aceptar la cadena 110101 (el carácter del extremo izquierdo es el primero en ser
analizado).
i. Diagrama de transición de estados
Ilustración 1 Diagrama de transición de estados – Ejercicio 2.3.3
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 14
Teoría de la Computación Taller 1
ii. Secuencia de estados para la cadena 110101
Entrada 1: q0 → q1
Entrada 1: q1 → q0
Entrada 0: q0 → q2
Entrada 1: q2 → q3
Entrada 0: q3 → q1
Entrada 1: q1 → q0
∴ La secuencia de estados para la cadena 110101 es:
q0 → q1 → q0 → q2 → q3 → q1 → q0
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 15
Teoría de la Computación Taller 1
3.4. AFD y lenguajes
3.4.1. Ejercicio 2.4.2
Construir los AFD que aceptan cada uno de estos lenguajes sobre {a, b}:
a) { w | toda a de w está entre dos bes}
Ilustración 2 Ejercicio 2.4.2 letra a.
b) { w | w contiene la subcadena abab}
Ilustración 3 Ejercicio 2.4.2 letra b.
c) { w | w no contiene ninguna de las subcadenas aa o bb}
Ilustración 4 Ejercicio 2.4.2 letra c.
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 16
Teoría de la Computación Taller 1
d) { w | w tiene un número impar de aes y un número par de bes}
Ilustración 5 Ejercicio 2.4.2 letra d.
e) { w | w tiene ab y ba como subcadenas}
Ilustración 6 Ejercicio 2.4.2 letra e.
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 17
Teoría de la Computación Taller 1
3.5. Autómata finito no determinista
3.5.1. Ejercicio 2.5.4
Sea M el AFN dado por Q = {q0 , q1 }, ⅀ = {a, b}, s = q0 , F= {q1 } y △ dada en la Figura
2.20. Determinar si a 2b, ba y b 2a están en L(M). Dibujar el diagrama de transición para
M.
△ a b
q0 {q0,q1} {q1}
q1 Ø {q0 ,q1 }
Tabla 2 Ejercicio 2.6.1
Diagrama de Transición:
Ilustración 7 Diagrama de Transición - Ejercicio 2.5.4
Se procede a comprobar si las siguientes palabras están en L(M):
a2b = ({q0 }, aab) ∝M ({q0 ,q1 },ab) ∝M ({q0 }, b) ∝M ({q1 }, 𝞮 )
A ∩ F = {q1 } ∩ {q1 } = {q1 }
Por lo cual sí está incluido en L(M).
ba = ({q0 }, ba) ∝M ({q1 }, a) ∝M ({ind}, 𝞮)
A ∩ F = {ind} ∩ {q1 } = {ind}
Por lo cual, no está incluido en L(M).
b2a = ({q0 }, bba) ∝M ({q1 },ba) ∝M ({q0 ,q1 }, a) ∝M ({q0 ,q1 }, 𝞮 )
A ∩ F = {q0 ,q1 } ∩ {q1 } = {q1 }
Por lo cual sí está incluido en L(M).
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 18
Teoría de la Computación Taller 1
3.6. Equivalencia de AFN y AFD
3.6.1. Ejercicio 2.6.1
Ilustración 8 Enunciado ejercicio 2.6.1
i. Diagrama de Transición
𝑄/∑ a b
𝑞𝑜 {𝑞𝑜 , 𝑞1 } {𝑞1 }
𝑞1 ∅ {𝑞𝑜 , 𝑞1 }
Tabla 3 Diagrama de transición
M = (Q, ∑, s, F, ∆)
Q = {𝑞𝑜 , 𝑞1 }
∑ = {𝑎, 𝑏}
s = 𝑞𝑜
F = {𝑞1 }
𝑄′/∑′ a b
𝑞𝑜′ ={𝑞𝑜 } {𝑞𝑜 , 𝑞1 }=𝑞1′ {𝑞1 } = 𝑞2
𝑞1′ ={𝑞𝑜 , 𝑞1 } {𝑞𝑜 , 𝑞1 }=𝑞1′ {𝑞𝑜 , 𝑞1 }=𝑞1′
𝑞2′ ={𝑞1 } ∅ {𝑞𝑜 , 𝑞1 }=𝑞1′
Tabla 4 Diagrama de conversión
M’ = (Q’, ∑′, s’, F’, δ)
Q’ = {𝑞𝑜′ , 𝑞1′, 𝑞2′ }
∑′ = {𝑎, 𝑏}
S’ = 𝑞𝑜′
F’ = {𝑞1′ 𝑞2′ }
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 19
Teoría de la Computación Taller 1
AFD Correspondiente:
Ilustración 9 AFD – Ejercicio 2.6.1.
𝑞1 = 𝑎𝑞1 | 𝑏𝑞1 = (𝑎 |𝑏)∗
𝑞2 = 𝑏𝑞1 = 𝑏(𝑎 |𝑏)∗
𝑞0 = 𝑎𝑞1 | 𝑏𝑞2 = 𝑎(𝑎 | 𝑏)∗ | 𝑏𝑏(𝑎 | 𝑏)∗ = (𝑎 | 𝑏𝑏)(𝑎 |𝑏)∗
Por lo tanto, la expresión regular para AFD será (𝑎 | 𝑏𝑏)(𝑎 | 𝑏)∗
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 20
Teoría de la Computación Taller 1
3.7. Transiciones
3.7.1. Ejercicio 2.7.5
Ilustración 10 Transiciones – Ejercicio 2.7.5
a) Tabla de transición para ∆ del AFN:
∆ a b c 𝜀
𝑞𝑜 {𝑞𝑜 } ∅ ∅ {𝑞1 }
𝑞1 ∅ {𝑞1 } ∅ {𝑞2 }
𝑞2 ∅ ∅ {𝑞2 } ∅
Tabla 5 Transición Ejercicio 2.7.5
b) ε - c(q0)= {q0,q1,q2}
• q0 es accesible desde q0 sin consumir nada.
• q1 es accesible desde q0 utilizando una transición ε.
• q2 es accesible desde q0 utilizando dos transiciones ε.
ε - c(q1)= {q1,q2}
• q1 es accesible desde q1 sin consumir nada.
• q2 es accesible desde q1 utilizando una transición ε.
ε - c(q2)= {q2}
• q2 es accesible desde q2 sin consumir nada.
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 21
Teoría de la Computación Taller 1
c) d(ε - c(q0), a) = {q0}
ε – c({q0}) = {q0, q1, q1}
Δ (q0, a) = {q0, q1, q1}
d(ε - c(q0), b) = {q1}
ε – c({q1}) = {q1, q2}
Δ (q0, a) = {q1, q2}
d(ε - c(q0), c) = {q2}
ε – c({q2}) = {q2 }
Δ (q0, a) = {q2}
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 22
Teoría de la Computación Taller 1
3.8. Autómatas finitos y expresiones regulares
3.8.1. Ejercicio 2.8.13
Ilustración 11 Ejercicio autómatas finitos y expresiones regulares – Ejercicio 2.8.13
Se definirá que:
• q0 Será representado por el punto de la izquierda Superior ⋅
• q1 Será representado por el punto de la abajo ⋅
• q2 Será representado por el punto de derecha Superior ⨀
Al evaluar:
a b
𝑞𝑜 𝑞2 𝑞1
𝑞1 𝑞1 𝑞1
𝑞2 𝑞𝑜 𝑞1
Tabla 6 Autómatas finitos y expresiones regulares.
Al utilizar la propiedad 𝑞1 (𝑟𝑠 ∪ 𝑟𝑡 = 𝑟(𝑠 ∪ 𝑡)):
𝑞1 = a𝑞1 b𝑞1 = 𝑞1 (𝑎|𝑏)
Al estar en constante recursión, se puede determinar lo siguiente:
𝑞1 (𝑎|𝑏) = (𝑎|𝑏)+
Se reemplaza 𝑞1 en el desarrollo de 𝑞𝑜 :
𝑞0 = a𝑞2 b𝑞1 = 𝑎(𝑎𝑞𝑜 | 𝑏(𝑎|𝑏)+ ) | 𝑏(𝑎|𝑏)+
= 𝑎2 (𝑞𝑜 ) | 𝑎𝑏(𝑎|𝑏)+ | 𝑏(𝑎|𝑏)+
𝑎2 𝑞0 al entrar en recursión se concluye que 𝑎2 𝑞0 = (𝑎2 )+
Entonces: 𝑞0 = (𝑎2 )+ | ab(𝑎|𝑏)+ | 𝑏(𝑎|𝑏)+
Por lo tanto, la expresión regular para AFD será (𝑎2 )+ | ab(𝑎|𝑏)+ | 𝑏(𝑎|𝑏)+.
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 23
Teoría de la Computación Taller 1
3.9. Propiedades de los lenguajes regulares
3.9.1. Ejercicio 2.9.2
Ilustración 12 Enunciado ejercicio 2.9.2
Independiente del valor que tome n o m, siempre serán 2b’s. De acuerdo con ello, se
aplicará el lema del bombeo y se le asignarán valores a n y m.
Por ejemplo, si n = 1 y m = 2, se generará la siguiente palabra:
w = 𝑎1 𝑏𝑎2 𝑏𝑎3 ∈ 𝐿
Al separar en 3 cadenas (xyz), queda:
x = 𝑎1 𝑏𝑎2 ; y = b; z = 𝑎3
Al bombear y una p cantidad de veces, con el primer bombeo, y queda: 𝑦 2 = 𝑏2
Si se unen las cadenas, ya no se cumplirá que sólo son 2b’s. Por lo que se puede concluir
a través del lema del bombeo que el enunciado no es un lenguaje regular.
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 24
Teoría de la Computación Taller 1
REFERENCIAS
Kelley. (1995). Teoría De Autómatas Y Lenguaje. Prentice Hall (Higher Education Division,
Pearson Education).
Preparado por Santiago V., Pailamilla G., Vera L., Vega B. 25