Tutorial Lenguajes Formales y Automatas

Contents
Chapter 1. Autómata finito 5

1. Alfabetos y lenguajes 5
2. Operaciones 6
3. Operaciones con lenguajes 8
4. Numerabilidad 14
5. Lenguajes Regulares y Expresiones Regulares 16
6. Autómatas finitos deterministas 23
7. Automatas finitos no deterministas 30
8. Equivalencia entre AFD y AFN 35
9. -transiciones 39
10. Autómatas finitos y expresiones regulares 48
11. Lema de Arden 56
12. Propiedades de los lenguajes regulares 62
Chapter 2. Lenguajes Independientes del Contexto 65
1. Gramáticas regulares 65
2. Gramáticas regulares y lenguajes regulares 69
3. Gramáticas independientes del contexto 74
4. Árboles de derivación ó análisis 76
5. Simplificación de las GIC 80
6. Eliminación de las producciones 86
7. Eliminación de producciones unitarias 89
Chapter 3. Máquinas de Turing 93
1. Definición y termininologı́a 93
2. Aceptación 96
1
Notas de Lenguajes Formales y Autómatas
César Bautista Ramos

Fac. Ciencias de la Computación, BUAP
CHAPTER 1
Autómata finito
Estudiaremos lenguajes formales, esto es “matemáticos”; no confundirlos con los

lenguajes naturales, que son los que habla la gente.
1. Alfabetos y lenguajes
Los lenguajes se forman de palabras y las palabras se forman de sı́mbolos de un
alfabeto.
Definición 1. Un alfabeto Σ es un conjunto no vacı́o y finito de sı́mbolos.
Ejemplo 1. El conjunto Σ = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}
es un alfabeto llamado alfabeto inglés.
Ejemplo 2. El conjunto Σ = {α, β, δ} es un alfabeto.
Ejemplo 3. El conjunto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} es un alfabeto.
Definición 2. Una palabra ó cadena sobre el alfabeto Σ es una sucesión
finita de sı́mbolos de Σ.
Ejemplo 4. La secuencia program es una palabra sobre el alfabeto inglés.
También digit, hda y quetzal son palabras sobre el alfabeto inglés, ası́ como bxweh.
En las sucesiones el orden es importante. Esto es, las palabras aba y aab se forman
de los mismos sı́mbolos: dos a y una b, pero su orden de aparición es diferente, por lo
que
aba 6= aab.
Este es un hecho general.
Ası́ como en la teorı́a de conjuntos hay que aceptar a la colección vacı́a como un
conjunto (el conjunto vacı́o ), en la teorı́a de lenguajes formales hay que aceptar a la
palabra vacı́a como una palabra genuina.
Definición 3. Si Σ es un alfabeto, la cadena vacı́a es una palabra sobre
Σ.
Enseguida definimos nuestro principal objeto de estudio.
Definición 4. Un lenguaje A sobre un alfabeto Σ es un conjunto de palabras
sobre Σ.
Ejemplo 5. Sea A = {1, 12, 123, 1234, 123456, 0}. El conjunto A es un lenguaje
sobre el alfabeto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. El conjunto B = {1, 11, 111, 1111, . . .}
es también un lenguaje (infinito) sobre Σ. Resulta que también es un lenguaje
sobre Σ.
5
6 1. AUTÓMATA FINITO
No debemos confundir a la palabra vacı́a con el lenguaje vacı́o:

6= .
Esta no igualdad será evidente cuando estudiemos las operaciones sobre lenguajes.
Resulta que la palabra vacı́a tiene propiedades muy diferentes a las del lenguaje vacı́o
.
Ejemplo 6. El conjunto A = {a, ab, aab, aaab, . . .} es un lenguaje (infinito)
sobre el alfabeto inglés Σ = {a, b, . . . , z}. También B = {} es un lenguajes sobre
Σ ası́ como también es un lenguaje sobre el alfabeto inglés.
Dado un alfabeto Σ uno puede considerar todas las posibles palabras formadas por
tal alfabeto. Se obtiene entonces un lenguaje universal.
Definición 5. Si Σ es un alfabeto, la cerradura de Σ ó lenguaje universal
sobre Σ se denota con
Σ∗
y este es el conjunto de todas las palabras sobre Σ:
Σ∗ = {w | w es una palabra sobre Σ}.
Nótese que
∀Σ alfabeto , ∈ Σ∗ .
Ejemplo 7. Si Σ = {1}, entonces
Σ∗ = {, 1, 11, 111, 1111, . . .}
2. Operaciones
Definición 6. Si w es una cadena sobre el alfabeto Σ, su longitud se denota
con |w|.
Ejemplo 8. Sea Σ = {0, 1, . . . , 9} y w = 121. Entonces |w| = 3. Además
|| = 0.
Definición 7. La concatenación de palabras es una operación “·”:
· : Σ∗ × Σ ∗ → Σ ∗
(w, z) 7→ w · z = wz
Ejemplo 9. Si w = aba y z = bad entonces w · z = ababad.
Es común omitir el sı́mbolo de la operación de concatenación. Por ejemplo, en el
anterior,
wz = ababad
Notemos las siguientes propiedades generales
(1) Si w, z son palabras entonces |wz| = |w| + |z|.
(2) Si w ∈ Σ∗ , entonces
(a) w = w
(b) w = w
(3) En general wz 6= zw.
2. OPERACIONES 7
Definición 8 (potencia). Si n ∈ y w ∈ Σ∗ , se define

(
si n = 0
wn = n−1
ww si n > 0
llamada la n-ésima potencia de w.
Ejemplo 10. Si w = 122 entonces
w0 =
w1 = ww0 = 122 = 122
w2 = ww1 = 122122
w3 = ww2 = 122122122
La igualdad entre palabras se podrı́a definir como: si w, z ∈ Σ ∗ , se pone w = z en

caso de que |w| = |z| y de que tengan los mismos sı́mbolos en la misma posición.
Definición 9. Sean w, x ∈ Σ∗ .
(1) Se dice que x es prefijo de w si ∃y ∈ Σ∗ tal que
w = xy
(2) Se dice que x es prefijo propio de w si x es prefijo de w, pero w 6= x.
Ejemplo 11. Sea w = 121. Entonces

(1) x = 1 es prefijo (propio) de w;
(2) u = 12 es prefijo (propio) de w;
(3) w = 121 es prefijo de w, pues w = w, pero no es propio.
Definición 10. Una cadena w ∈ Σ∗ es subpalabra de z ∈ Σ∗ si ∃x, y ∈ Σ∗

tales que
z = xwy
Ejemplo 12.
(1) Si w ∈ Σ∗ entonces w es subpalabra de la misma w, pues
w = w
(2) w = 2 es subpalabra de z = 121; a su vez y = 12 es subpalabra de z, pues

z = y1.
El siguiente concepto será útil para definir nuevos lenguajes.
Definición 11. Si w ∈ Σ∗ , la inversa o transpuesta de w es la imagen

reflejada de w que se denota w I . Esto es:
(
I w si w =
w =
y a si w = ax con a ∈ Σ y y ∈ Σ∗
I
Ejemplo 13. Si w = ecos, entonces

wI = (cos)I e
= (os)I ce
= sI oce
= (s)I oce
= I soce
= soce
= soce
Propiedad 1. Si w, y ∈ Σ∗ , entonces
(wy)I = y I wI
Proof. Por inducción sobre n = |w|. Si n = 0, entonces w = , luego
(wy)I = (y)I
= yI
mientras que
wI y I = y I , por definición,
= yI
por lo tanto (wy)I = wI y I .
Supongamos cierto el resultado para palabras w0 de longitud n: esto es
(1) (w0 y)I = y I w0I
Ahora tomemos una palabra w de longitud |w| = n+1. Entonces w = az con a ∈ Σ
y z ∈ Σ∗ con |z| = n. Luego
(wy)I = (azy)I
= (zy)I a, por definición de inversa,
I I
= y z a, por hipótesis de inducción (1),
I I
= y (az) , por definición de inversa
I I
=y w .

3. Operaciones con lenguajes

Ası́ como las palabras se pueden concatenar, también se puede hacer una operación
similar sobre lenguajes.
Definición 12. Si A es lenguaje sobre el alfabeto Σ1 y B es lenguaje sobre el
alfabeto Σ2 , se define el lenguaje concatenación de A con B como
A · B = {w · w | w ∈ A y x ∈ B}
sobre el alfabeto Σ1 ∪ Σ2 .
3. OPERACIONES CON LENGUAJES 9
Esto es, el lenguaje A · B está formado por todas las posibles concatenaciones de
las cadenas de A con las de B. También, como en la concatenación de cadenas, el
sı́mbolo de concatenación “·” se acostumbra omitir y se pone AB = A · B.
Ejemplo 14. Si A = {casa}, B = {pajaro, perro}, entonces
AB = {casapajaro, casaperro}
Entre los lenguajes, el lenguje {} se comporta como 1 con respecto a la operación
de concatenación.
Propiedad 2. Si A es un lenguaje arbitrario, entonces
A{} = A = {}A.
Proof.
A{} = {w | w ∈ A}, por definición de concatenación,
= {w | w ∈ A}
= A;
similarmente se prueba {}A = A.

También se puede hablar de potencia de un lenguaje:
Definición 13. (potencia) Sea n ∈ :
(
n {}, si n = 0
A =
A · An−1 , si n ≥ 1
Ejemplo 15.
(1) 0 = {}
(2) Sea A = {ab} lenguaje formado por sólo una palabra. Entonces
A0 = {}
A1 = A · A0 = A{} = A = ab
A2 = A · A1 = A{ab} = abab
A3 = A · A2 = A{abab} = ababab
etcétera.
Definición 14. Sean A, B lenguajes. Entonces
(1) El lenguaje unión es:
A ∪ B = {x | x ∈ A ∨ x ∈ B}
(2) El lenguaje intersección es
A ∩ B = {x | x ∈ A ∧ x ∈ B}
(3) El lenguaje diferencia es
A − B = {x | x ∈ A ∧ x 6∈ B}
Ejemplo 16. Sea Σ = {0, 1} y lenguajes A = {, 0, 10, 11}, B = {, 1, 0110, 11010}.
Luego,
A ∪ B = {, 0, 1, 10, 11, 0110, 11010}
A ∩ B = {, 1}
A − B = {0, 10, 11}
B − A = {0110, 11010}
En general, como los lenguajes son conjuntos, los lenguajes heredan todas las
propiedades y terminologı́a de los conjuntos.
Definición 15. Sean A, B lenguajes sobre un alfabeto Σ. Si A ⊆ B, entonces
se dice que A es sublenguaje de B.
Ejemplo 17. Sea A = {a, aa, aaa, aaaa, aaaaa} y B = {a n | n ∈ }, entonces
A es sublenguaje de B.
En general, si L es un lenguaje sobre un alfabeto Σ entonces L es un sublenguaje
de Σ∗ .
También, recordemos que de la definición de la igualdad de conjuntos podemos
obtener que dos lenguajes A, B son iguales: A = B si y sólo si
(1) A ⊆ B
(2) B ⊆ A
Esta observación nos ayudará a demostrar el siguiente teorema.
Teorema 1. Sean A, B, C lenguajes sobre un alfabeto Σ. Se cumple que
(1) A · (B ∪ C) = (A · B) ∪ (A · C)
(2) (B ∪ C) · A = (B · A) ∪ (C · A)
Proof.
(1) Por contenciones, esto probaremos que
(a) A · (B ∪ C) ⊂ (A · B) ∪ (A · C)
(b) (A · B) ∪ (A · C) ⊂ A · (B ∪ C)
(a): Si x ∈ A · (B ∪ C) entonces x = w · y con w ∈ A y y ∈ B ∪ C; luego
y ∈ B ó y ∈ C. Si y ∈ B entonces x = wy ∈ A · B; y si y ∈ C,
entonces x = w · y ∈ A · C, ası́,
x ∈ (A · B) ∪ (A · C)
(b): Si x ∈ (A · B) ∪ (A · C) entonces x ∈ A · B ó x ∈ A · C. Si x ∈ A · B
entonces x = wy con w ∈ A y y ∈ B ⊆ B ∪ C, luego x = wy con
w ∈ A y y ∈ B ∪ C.
Si x ∈ A · C entonces x = wy con w ∈ A y y ∈ C ⊆ B ∪ C, entonces
x = wy con w ∈ A y y ∈ B ∪ C, luego x ∈ A · (B ∪ C).
En cualquier caso
x ∈ A · (B ∪ C).
(2) Tarea.

Notemos que en general, no es cierto que
A · (B ∩ C) = (A · B) ∩ (A · C)
por la culpa del contrajemeplo siguiente: A = {a, }, B = {}, C = {a}, entonces
B ∩ C = y ası́
A · (B ∩ C) =
mientras que A · B = A = a, y A · C = {aa, a}, por lo que
(A · B) ∩ (A · C) = {a} 6= A · (B ∩ C)
Uno de los concepto fundamentales de la teorı́a es el de cerradura.
Definición 16. Sea A lenguaje sobre el alfabeto Σ.
(1) La cerradura de Kleene o cerradura estrella de A es
A∗ = ∪ ∞
n=0 A
n
(2) La cerradura positiva de A es

A+ = ∪ ∞
n=1 A
n
La cerradura de Kleene se obtiene al hacer cero o más concateneaciones de las

palabras de A, mientras que la cerradura positiva se obtiene al hacer una o más con-
catenaciones.
Ejemplo 18. A = {a}. Entonces A0 = {}, A1 = a, A2 = aa, A3 = aaa, . . .
entonces
A∗ = {, a, a2 , a3 , . . .}
mientras que
A+ = {a, a2 , a3 , . . .}
Ejemplo 19. Sea Σ un alfabeto. En particular el propio Σ es un alfabeto
formado por las palabras de longitud 1. Luego la cerradura de Kleene de Σ es
∪∞
n=0 Σ
n
que es junto con todas las concatenaciones de palabras sobre Σ que es precisamente
el lenguaje universal Σ∗ . Este razonamiento muestra que nuestra notación para el
lenguaje universal es consistente con la notación de la cerradura de Kleene:
Σ∗
|{z} = Σ∗
|{z}
lenguaje universal cerradura de Kleene
Propiedad 3. Si A es un lenguaje sobre Σ, entonces

(1) A∗ ⊆ Σ∗
(2) A+ ⊆ A∗
Proof.
(1) ∀n ≥ 0, An ⊆ Σ∗ , entonces
A∗ = ∪ ∞
n=0 ⊂ Σ
∗
]
(2) f orallk ≥ 1, Ak ⊆ ∪n=0 ∞An = A∗ , entonces
A+ = ∪ ∞
k=1 ⊆ A
∗

Ejemplo 20. Tenemos que es un lenguaje. Entonces

0 1 2
= {}, = , = ,...
por lo que
∗ +
= {}, =
Uno podrı́a pensar que la diferencia entre la cerradura de Kleene y la cerradura
positiva es la palabra vacı́a . Esto no siempre es cierto, como puede notarse en el
siguiente ejemplo.
Ejemplo 21. Sea Σ = {0, 1, . . . , 9}, y consideremos el lenguaje
A = {w ∈ Σ∗ | w no contiene ninguno de los dı́gitos 0, 1, . . . , 9}
Luego, ∈ A, 0 ∈ A, 1 ∈ A, 01010100111 ∈ A. Nos proponemos demostrar que
A∗ = A + .
Si k ≥ 1 y x ∈ Ak , entonces x = w1 · · · wk con cada wi ∈ A cadena conteniendo
sólo 0’s y 1’s. Luego x contiene sólo 0’s y 1’s. Por lo tanto,
∀k ≥ 1, Ak ⊆ A .
Además, si k ≥ 1 y x ∈ A, entonces x = k−1 x ∈ Ak , esto es A ⊆ Ak :
∀k ≥ 1, Ak = A
Por lo que
A+ = ∪ ∞ k
n=1 A = A .
Pero también, como A0 = {} ⊆ A, se sigue
A∗ = A 0 ∪ A +
= A0 ∪ A
=A
por lo tanto
A∗ = A = A +
Como puede notarse del ejemplo anterior en algunos casos A + = A∗ .
Lema 1. Sean A, A0 , A1 , . . . una colección infinita de lenguajes sobre Σ. En-
tonces
(1) A · ∪∞ ∞
n=0 An = ∪n=0 A · An
(2) (∪n=0 An ) · A = ∪∞
∞
n=1 An · A
Proof.
(1) Por demostrar
(a) A · ∪∞ ∞
n=0 An ⊆ ∪n=0 A · An
(b) ∪n=0 A · An ⊆ A · ∪∞
∞
n=1 An
(a): Si x ∈ A · ∪∞ ∞
n=0 An , entoces x = w · y con w ∈ A y y ∈ ∪n=0 An , luego
existe k0 tal que y ∈ Ak0 , ası́ x = wy ∈ A · Ak0 , lo que implica que
x ∈ ∪∞
n=0 A · An .
(b): Si x ∈ ∪∞
n=0 A · An entonces existe k0 tal que x ∈ A · Ak0 , por lo que
x = wy con w ∈ A y y ∈ Ak0 , es decir y ∈ ∪∞n=0 An . Ası́
x ∈ A · ∪∞
n=0 An
Por lo tanto
A · ∪∞ ∞
n=0 An = ∪n=0 A · An .
(2) Tarea.

Teorema 2.
A+ = A · A ∗ = A ∗ · A
Proof.
A · A∗ = A · ∪ ∞
n=0 A
n
= ∪∞
n=0 A · A
n
= ∪∞
n=0 A
n+1
= ∪∞
k=1 A
k
= A+ .
y similarmente A∗ · A = A+ .

Ejemplo 22. Sea {A} = {ab} lenguaje sobre el alfabeto inglés. Tenemos que
A+ = {ab, abab, ababab, . . .} = {(ab)i | i ≥ 1}
el cual es a su vez un lenguaje. Podemos considerar sus potencias
(A+ )2 = A+ · A+
= {ab · ab, ab · abab, ab · ababab, . . . , abab · ab, abab · abab, abab·, ababab, . . . , }
el cual es un sublenguaje de A+ : (A+ )2 ⊆ A+ . De forma similar (A+ )3 ⊆ A+ ,
(A+ )4 ⊆ A+ , . . .. Este es un hecho general.
Lema 2. Sea A un lenguaje. Entonces
(A+ )k ⊆ A+ , ∀k ≥ 1
Proof. Por inducción sobre k. Si k = 1:
(A+ )k = (A+ )1 = A+ ⊆ A+ .
También el resultado es cierto para k = 2:
(A+ )2 = A+ · A+
= A + · ∪∞
n=1 A
n
= ∪∞ +
n=1 A · A
n
n
= ∪∞ ∞
n=1 ∪j=1 A
j
·A
∪∞ ∞ j
n=1 ∪j=1 A · A
n
= ∪∞ ∞
n=1 ∪j=1 A
j+n
⊆ ∪∞
m=1 A
m
= A+
Supongamos cierto que
(A+ )k ⊆ A+ .
Por demostrar que (A+ )k+1 ⊆ A+ . Tenemos que

(A+ )k+1 = A+ · (A+ )k
⊆ A + · A+
= (A+ )2
⊆ A+

Tarea 1. Sea x ∈ Σ∗ . Demostrar que (xI )I = x.
Definición 17. Si A es un lenguaje, su inverso es
AI = {wI | w ∈ A}
Propiedad 4. Si A, B son lenguajes, entonces
(A · B)I = B I · AI
Proof. Por contenciones, demostraremos que
(1) (A · B)I ⊆ B I · AI
(2) B I · AI ⊆ (A · B)I
(1) Sea z ∈ (A · B)I , entonces z = xI con x ∈ A · B, por lo que x = yw con
y ∈ A y w ∈ B. Luego
z = (yw)I
= w I y I ∈ B I · AI
Por lo tanto (A · B)I ⊆ B I · AI .

(2) Sea z ∈ B I · AI , entonces z = w I · y I con w ∈ B y y ∈ A. Por lo que
z = wI y I = (yw)I ∈ (A · B)I .
Por lo tanto B I · AI ⊆ (A · B)I .

4. Numerabilidad
Nos proponemos estudiar lo siguientes problemas:
(1) Dado un lenguaje A y x ∈ Σ∗ , ¿x ∈ A∗
(2) Dado un lenguaje A, especificar qué palabras lo componen.
Ejemplo 23. Sea Σ = {a, b}.
(1) ¿Cuántas palabras de longitud 0 hay?: . Sólo una.
(2) ¿Cuántas palabras de longitud 1 hay?: a, b. Dos.
(3) ¿Cuántas palabras de longitud 2 hay?: aa, ab, ba, bb. 4
(4) ¿Cuántas palabras de longitud 3 hay?: 8
(5) ¿Cuántas palabras de longitud n hay?: 2n .
Podemos numerar las palabras de Σ∗ según el siguiente orden
a < ab, aa < ab, a ≤ baaaa
4. NUMERABILIDAD 15
Podemos enumerar las palabras según este orden

7→ 0
a 7→ 1
b 7→ 2
aa 7→ 3
ab 7→ 4
ba 7→ 5
bb 7→ 6
aaa 7→ 7
..
.
Sin embargo, por comodidad (para el caso general) también podemos enumerar
usando números en base 3
7→ 0
a 7→ 1
b 7→ 2
aa 7→ 113 = 4
ab 7→ 123 = 5
ba 7→ 213 = 7
bb 7→ 223 = 8
aaa 7→ 1113 = 13
..
.
Supongamos que Σ = a1 , a2 , . . . , an . Podemos enumerar las palabras de Σ∗ con
números en base n + 1 como
7→ 0
a1 7→ 1
a2 → 7 2
..
.
an 7→ n
a1 a1 7→ 11n+1
a1 a2 7→ 12n+1
..
.
es decir, tenemos una función
f : Σ∗ →
la cual es inyectiva, pues cada numero natural tiene una única representación en base.
De donde se sigue que Σ∗ es enumerable.
Teorema 3. Si Σ es un alfabeto entonces Σ∗ es infinito numerable.
En contraste todos los lenguajes que se pueden formar con Σ no es numerable. Es

decir, hay mucho más lenguajes que palabras. Se puede demostrar esto, usando lo que
se llama la técnica de diagonalización.
Teorema 4. Sea Σ un alfabeto. El conjunto de los lenguajes sobre Σ no es

numerable.
Proof. Sea
L = {A | A es lenguaje sobre Σ} .
Procedemos por contradicción. Supongamos que L es numerable. Entonces
L = {A0 , A1 , A2 , . . .} .
Sabemos que Σ∗ es numerable, entonces podemos poner
Σ∗ = {w0 , w1 , w2 , . . .}
definimos entonces el conjunto diagonal,
D = {wi ∈ Σ∗ | wi 6∈ Ai } ⊆ Σ∗
D es un lenguaje sobre Σ∗ , entonces D ∈ L, por lo que debe de existir k ∈ tal

que
D = Ak .
Tenemos dos casos wk ∈ D o wk 6∈ D.

(1) Si wk ∈ D entonces wk 6∈ Ak = D, i.e., wk 6∈ D: absurdo.
(2) Si wk 6∈ D = Ak entonces wk ∈ D: absurdo de nuevo
En cualquier caso obtenemos un absurdo. Por lo tanto L no es numerable.

5. Lenguajes Regulares y Expresiones Regulares

Definición 18. Sea Σ un alfabeto. El conjunto de los lenguajes regulares
se define como:
(1) es un lenguaje regular;
(2) {} es un lenguaje regular;
(3) ∀a ∈ Σ, {a} es un lenguaje regular;
(4) Si A, B son lenguajes regulares entonces
A ∪ B, A · B, A∗
son lenguajes regulares.
Esto es, el conjunto de los lenguajes regulares sobre Σ está formado por el lenguajes
vacı́o, los lenguajes unitarios incluidos {} y todos aquellos obtenidos de estos por
concatenación, unión y la cerradura de Kleene de éstos.
5. LENGUAJES REGULARES Y EXPRESIONES REGULARES 17
Ejemplo 24. Sea Σ = {a, b}. Entonces

, {} son lenguajes regulares
{a}, {b} son lenguajes regulares
{a, b} es lenguaje regular pues {a.b} = {a} ∪ {b}
{ab} es regular pues {ab} = a · {b}
{a, a, b, b} = {a, b} ∪ {ab} es regular
| {z } |{z}
regular regular
{a | i ≥ 0} = {a}∗ es regular
i
{ai bj | i ≥ 0 y j ≥ 0} = {a}∗ · {b}∗ es regular

|{z} |{z}
regular regular
{(ab) | i ≥ 0} = {ab}∗ es regular .

i
Ejemplo 25. Sea Σ = {a, b, c} y A el lenguaje sobre Σ:

A = {w ∈ Σ∗ | w no tiene a ac como subcadena}
¿Es A regular?
Sol. Notemos que
{b}{c}∗ ⊆ A y {a}∗ ⊆ A
luego las palabras formadas por concatenaciones de potencias ai y bcj están en A;
i.e.,
({a} ∪ {b}{c}∗)∗ ⊆ A
luego
{c}∗ ({a} ∪ {b}{c}∗)∗ ⊆ A .
Probaremos que
A = {c}∗ ({a} ∪ {b}{c}∗)∗
y ası́ resultará que A es regular. Sólo falta comprobar que
(2) A ⊆ {c}∗ ({a} ∪ {b}{c}∗)∗ .
Sea w ∈ A, entonces w = ci w0 para algún i ≥ 0 y w 0 palabra que no tiene a c
como prefijo. Ası́, w 0 está formada por a’s, b’s y c’s donde cualquier bloque de c’s
no puede seguir a a’s, en consecuencia, cualquier bloque de c’s sigue a b0 s, de donde
w0 ∈ ({a} ∪ b{c}∗ )∗
entonces
w = ci w0 ∈ {c}∗ ({a} ∪ {b}{c}∗)∗ ,
por lo tanto
A = {c}∗ ({a} ∪ {b}{c}∗)∗
que es un lenguaje regular.
Las expresiones regulares se definen como sigue
Definición 19. Sea Σ un alfabeto.
(1) y son expresiones regulares;
(2) Si a ∈ Σ entonces a es una expresión regular;
(3) Si r y s son expresiones regulares entonces

r ∪ s, r · s, r∗
son expresiones regulares.
Como en las concatenaciones, a veces escribiremos
rs = r · s
Ejemplo 26. Sea Σ = {a, b, c}. Entonces
c∗ (a ∪ bc∗ )∗
es una expresión regular.
Proof. Tenemos que b es una expresión regular, ası́ como c, entonces c∗ es
una expresión regular por lo que bc∗ también. Lo es también a, luego a ∪ bc∗ es

expresión regular y en consecuencia (a ∪ bc∗ )∗ es regular. Finalmente c∗ (a ∪ bc∗ )∗
es expresión regular.
as expresiones regulares son nombres para los lenguajes regulares.
Definición 20. Sea Σ un lenguaje. El lenguaje L de una expresión regular
sobre Σ se define como:
(1) L( ) = , L() = {};
(2) Si a ∈ Σ, L(a) = {a};
(3) Si r, s son expresiones regulares entonces
(a) L(r ∪ s) = L(r) ∪ L(s)
(b) L(rs) = L(r)L(s)
(c) L(r∗ ) = L(r)∗
Para calcular los lenguajes de expresiones regulares se hace uso del orden de prece-
dencia:
(1) cerraduras de Kleene: ∗
(2) concatenaciones :·
(3) uniones: ∪
Ejemplo 27.
L(a ∪ ab∗ ) = L(a) ∪ (L(a) · L(b)∗ )
Definición 21. Si r es una expresión regular entonces
r+ = rr∗
Propiedad 5.
L(r+ ) = L(r)+
Proof. Por definición
L(r+ ) = L(rr∗ )
= L(r)L(r∗ )
= L(r)L(r)∗
= L(r)+

Definición 22. Sean r, s expresiones regulares sobre Σ. Se dice que r y s son

equivalentes si y sólo si L(r) = L(s) en tal caso se escribe r = s. Es decir,
r = s ⇔ L(r) = L(s)
Notemos que r = s ⇔
(1) L(r) ⊆ L(s)
(2) L(s) ⊆ L(r)
También es fácil ver que si r es una expresión regular entonces L(r) es un lenguaje
regular.
Ejemplo 28.
(a∗ b)∗ = ∪ (a ∪ b)∗ b
Proof. El alfabeto bajo consideración es Σ = {a, b}. Por definición
L((a∗ b)∗ ) = ({a}∗ {b})∗
que es el lenguaje formado por 0 o más concatenaciones de palabras de {a} ∗ b esto
es, palabras del tipo

a j1 b · · · a jk b
esto es, la palabra vacı́a junto con palabras que terminan en b. Este lenguaje es la
descripción exactamente del lenguaje regular siguiente
{} ∪ ({a, b}∗ · {b}) = L( ∪ (a ∪ b)∗ b)
de donde
L((a∗ b)∗ ) == L( ∪ (a ∪ b)∗ b)
por lo tanto
(a∗ b)∗ = ∪ (a ∪ b)∗ b

Ejemplo 29. Sea r ena expresión regular, entonces
r+ = r∗ r
Proof. Por la propiedad 5
L(r+ ) = L(r)+
= L(r)∗ L(r)
= L(r∗ r)
lo que implica que r + = r∗ r.

El álgebra de las expresiones regulares viene descrita en el siguiente teorema.
Teorema 5. Sean r, st expresiones regulares sobre Σ. Entonces
(1) r ∪ s = s ∪ r
(2) r ∪ = r = ∪ r
(3) r ∪ r = r
(4) (r ∪ s) ∪ t = r ∪ (s ∪ t)
(5) r = r = r
(6) r = = r
(7) r(st) = (rs)t

(8) r(s ∪ t) = rs ∪ rt y (r ∪ s)t = rs ∪ st
(9) r∗ = r∗ ∗ = r∗ r∗ = ( ∪ r)∗ = r∗ (r ∪ ) = (r ∪ )r ∗ = ∪ rr∗
(10) (r ∪ s)∗ = (r∗ ∪ s∗ )∗ = (r∗ s∗ )∗ = (r∗ s)∗ r∗ = r∗ (sr∗ )∗
(11) r(sr)∗ = (rs)∗ r
(12) (r∗ s)∗ = ∪ (r ∪ s)∗ s
(13) (rs∗ )∗ = ∪ r(r ∪ s)∗
(14) s(r ∪ )∗ (r ∪ ) ∪ s = sr ∗
(15) rr∗ = r∗ r
Proof. Sólo haremos la demostración de una de estas equivalencias. La demás
son similares.
(11) Por demostrar que
(3) L(r(sr)∗ ) = L((rs)∗ r)
Sea w ∈ L(r(sr)∗ ) = L(r)(L(s)L(r))∗ entonces
w = r 0 s1 r1 s2 r2 · · · s n rn
con r0 ∈ L(r) y cada si ∈ L(s), ri ∈ L(r). Podemos escribir
w = (r0 s1 ) · (r1 s2 ) · · · (rn−1 sn−1 )rn
∈ (L(r) · L(s))∗ L(r) = L((rs)∗ r)
Por lo tanto,
L(r(sr)∗ ) ⊆ L((rs)∗ r) .
Similarmente se prueba que L((rs)∗ r) ⊆ L(r(sr)∗ ). Se sigue entonces que
la ecuación (3) es cierta. Se concluye entonces que
r(sr)∗ = (rs)∗ r

Como un ejemplo del uso de ésta álgebra es la siguiente propiedad.
Propiedad 6. Si r = s∗ t entonces r = sr ∪ t
Proof.
r = s∗ t = (s+ ) pues L(s∗ ) = L() ∪ L(s+ )
= ( ∪ ss∗ )t por definición de s+
= t ∪ ss∗ t por (5) e hipótesis
= sr ∪ t por (1)

Tarea 2. (1) ¿De que conjunto de sı́mbolos se derivan las frases ingle-
sas?
(2) ¿Por qué el lenguaje vacı́o no es el mismo que {}?
(3) ¿Sea Σ = {1}. ¿Se puede decir que para todo número natural n hay
alguna palabra w ∈ Σ∗ para la cual |w| = n? ¿es única? ¿Qué ocurrirı́a
si Σ = {1, 2}?
(4) Para una palabra w, ¿se puede decir que

|wi+j | = |wi | + |wj |?
Encontrar una expresión para |w i+j | en términos de i, j y |w|.
(5) ¿La cadena vacı́a es un prefijo de sı́ misma?
(6) Definir las nociones de sufijo y sufijo propio de una cadena sobre un alfa-
beto. Dar ejemplos.
(7) Obtener todos los prefijos, sufijos y subpalabras de la palabra w = bar
sobre el alfabeto inglés.
Tarea 3.
(1) Sea x ∈ Σ∗ . Probar que (xI )I = x.
(2) Para un lenguaje arbitrario A, ¿qué es A · ?
(3) Sean A = {el, mi} y B = {caballo, casa, herradura} lenguajes sobre el
alfabeto ingés. Obtener A · B, A · A y A · B · B.
(4) Suponer que A = {, a}. Obtener An para n = 0, 1, 2, 3 ¿Cuántos elemen-
tos tiene An para n arbitrario? ¿Cuáles son las cadenas de An para n
arbitrario?
(5) Sea A = {}. Obtener An para n arbitrario.
(6) Sean A = {, ab} y B = {cd} ¿Cuántas cadenas hay en An · B para n
arbitrario?
(7) Sean A = {a}, B = {b}. Obtener An B, AB n y (AB)n .
(8) Sean A = {}, B = {aa, ab, bb}, C = {, aa, ab} y D = el lenguaje
vacı́o. Obtener A ∪ B, A ∪ C, A ∪ D y A ∩ B, B ∩ C, C ∩ D, A ∩ D.
Suponer que F es un lenguaje cualquiera. Obtener F ∪ D y F ∩ D.
(9) ¿Bajo qué condiciones A∗ = A+ ?
(10) Obsérvese que para todo lenguaje A se tiene que ∈ A∗ ¿cuándo ∈ A+ ?
(11) Probar que {}∗ = {} = {}+ .
(12) Antes se obtuvo que A∗ = A0 ∪ A+ = {} ∪ A+ . Cabrı́a esperar que A+ =
A − {}. Probar que, en general, ésta expresión no es cierta. ¿Cuándo se
cumplirá que A+ = A∗ − {}.
(13) Obtener lenguajes A, B, C tales que A · (B − C) 6= A · B − A · C.
(14) Probar que
(a) (A∗ )∗ = A∗
(b) (A∗ )+ = A∗
(c) (A+ )∗ = A∗
(15) Demostrar que se cumplen las siguientes igualdades para los lenguajes A
y B sobre el alfabeto Σ:
(a) (A ∪ B)I = AI ∪ B I
(b) (A ∩ B)I = AI ∩ B I
(c) (A+ )I = (AI )+
(d) (A∗ )I = (AI )∗
Tarea 4.
(1) Sea Σ = {a, b}. Lo siguiente es una definición recursiva del lenguaje A:
(a) ∈ A.
(b) Si x ∈ A, entonces axb y bxa pertenecen a A.
(c) Si x e y pertencen a A, entonces xy pertenece a A.
(d) No hay nada más en A.
Probar que
(a)
A = {w ∈ Σ∗ | w tiene el mismo número de aes que de bes}
(b) Si b y están en A ¿qué más palabras hay en A?
(c) Dar una definición recursiva para que A ⊆ {a, b}∗ contenga todas las
palabras que tienen el doble de aes que bes
(2) Un palı́ndromo es una cadena que se lee igual hacia adelante que hacia
atrás. Por ejemplo, la palabra “a” es un paı́ndromo, al igual que la cadena
“radar”. Dar una definición recursiva de un palı́ndromo (obsérvese que
es un palı́ndromo).
(3) Probar que para los lenguajes A y B, (A ∪ B)∗ = (A∗ B ∗ )∗ .
Tarea 5.
(1) Verificar, aplicando la definición de lenguaje regular, que los siguientes
son lenguajes regulares sobre Σ = {a, b}:
(a) {ai | i > 0}.
(b) {ai | i > n} para n ≥ 0 fijo.
(c) {w ∈ Σ∗ | w termina con a}.
(2) Verificar que el lenguaje de todas las cadenas de ceros y unos que tienen
al menos dos ceros consecutivos, es un lenguaje regular.
(3) Los identificadores de Pascal son cadenas de longitud arbitraria compues-
tas por caracteres alfabéticos y por dı́gitos. Los identificadores de Pascal
deben empezar con un carácter alfabético. ¿Es este un lenguaje regular?
(4) Obtener una expresión regular que represente el lenguaje de los identifi-
cadores de Pascal.
(5) (a) Probar que (r ∪ )∗ = r∗ .
(b) Probar que (b ∪ aa∗ b) ∪ (b ∪ aa∗ b)(a ∪ ba∗ b)∗ (a ∪ ba∗ b) y a∗ b(a ∪ ba∗ b)∗
son equivalentes.
(c) Sobre Σ = {a, b, c} ¿son equivalentes las parejas de expresiones regu-
lares de cada apartado?
(d) (a ∪ b)∗ a∗ y ((a ∪ b)a)∗ .
(e) ∗∗ y .
(f) ((a ∪ b)c)∗ y (ac ∪ bc)∗ .
(g) b(ab ∪ ac) y (ba ∪ ba)(b ∪ c).
(6) Simplificar:
(a) ∗ ∪ a∗ ∪ b∗ ∪ (a ∪ b)∗ .
(b) ((a∗ b∗ )∗ · (b∗ a∗ )∗ )∗ .
(c) (a∗ b)∗ ∪ (b∗ a)∗ .
(d) (a ∪ b)∗ a(a ∪ b)∗ .
(7) Probar que (aa)∗ a = a(aa)∗ .
(8) Simplificar las siguientes expresiones regulares:
(a) ( ∪ aa)∗ .
(b) ( ∪ aa)( ∪ aa)∗ .
(c) a( ∪ aa)∗ a ∪ .
(d) a( ∪ aa)∗ ( ∪ aa) ∪ a.
(e) (a ∪ )a∗ b.
(f) ( ∪ aa)∗ ( ∪ aa)a ∪ a.
(g) ( ∪ aa)( ∪ aa)∗ ( ∪ aa) ∪ ( ∪ aa).
6. AUTÓMATAS FINITOS DETERMINISTAS 23
(h) ( ∪ aa)( ∪ aa)∗ (ab ∪ b) ∪ (ab ∪ b).

(i) (a ∪ b)(aa)∗ ( ∪ aa) ∪ (a ∪ b).
(j) (aa)∗ a ∪ (aa)∗ .
(k) a∗ b((a ∪ b)a∗ b)∗ ∪ a∗ b.
(l) a∗ b((a ∪ b)a∗ b)∗ (a ∪ b)(aa)∗ ∪ a(aa)∗ ∪ a∗ b((a ∪ b)a∗ b)∗ .
6. Autómatas finitos deterministas

Nuestro problema principal es determinar si una palabra pertenece ó no a un
lenguaje. Por ejemplo, si A es el lenguaje de la expresión regular c ∗ (a ∪ bc∗ )∗ en-
tonces
abc5 c3 ab ∈ A, cabac3 bc 6∈ A,
el análisis se puede hacer letra por letra según sus posiciones. Para ayudar a tal anásisis
se hace uso de grafos dirigidos llamados diagramas de transición. Los nodos de tales
grafos se llaman estados, las flechas se llaman transiciones y se etiquetan éstas flechas
con sı́mbolos del alfabeto.
Hay sı́mbolos especiales: estado inicial que se marca con → y estados finales ó
de aceptación que se marcan con un cı́rculo: si
Por ejemplo:
Figure 1. Un autómata finito determinista
Tales grafos se llaman autómatas finitos deterministas (AFD).

Una palabra se dice aceptada ó legal con respecto a un AFD si partiendo del
estado marcado como inicial, se llega a un estado de aceptación mediante el siguiente
procedimiento:
¿la cadena aba es aceptada por el AFD de la figura 6? comenzando del nodo
marcado como estada inicial seguimos el camino indicado por las flechas con etiquetas
las letras de la palabra en cuestión:
se arriba entonces a un estado que no es de aceptación, por lo que la palabra aba

se rechaza.
¿a3 b es aceptada? veamos el diagrama:
como se puede notar, tal palabra nos hace llegar al estado de aceptación, por lo
que la palabra a3 b es aceptada.
De donde es claro que el autómata finito determinista de la figura 6 acepta las
palabras del lenguaje de a∗ b.
Ejemplo 30. Sea Σ = {a, b}. Consideremos el lenguaje
A = {(ab)i | i ≥ 1} .
Construir un AFD que acepte únicamente a las palabras de A.
Sol. Recordemos que
A = {ab, abab, ababab, . . .}
de donde al menos la palabra ab debe, en el autómata que construyamos, conducir
a un estado de aceptación. Lo que sugiere que consideremos el diagrama
éste aún no es un AFD, puesto que se requiere que el autómata, en cada estado,
sepa a qué estado nuevo se transita ante la aparición de cualquier letra del alfabeto,
en nuestro caso a y b. Notemos que en nuetro primer diagrama el autómata, en
el estado inicial no sabrá que hacer si aparece una b. Ninguna palabra de A tiene
prefijo b, luego las palabras que comiencen con b, sin importar lo que siga, deben
de ser rechazadas. Esto sugiere:
Otras palabras a rechazar son aquellas que después de a, en lugar de continuar con
b, continuen con a, lo que sugiere
Otras palabras que deben de ser aceptadas son por ejemplo abab, ababab. La manera
de crear repeticiones es introducir ciclos en el grafo:
con lo cual aceptamos las palabras del tipo (ab)+ . Pero aún debemos rechazar las
palabras que al tener prefijo ab continuen con b:
lo que completa nuestro autómata finito determinista que acepta solamente las
palabras del lenguaje de (ab)+ .
Ejemplo 31. Lo mismo que el anterior para A = (ab)∗ .

Sol. Ahora la palabra vacı́a también tiene que ser aceptada. La técnica para
aceptar a es hacer al estado inicial, final también:
Por lo que el autómata pedido es
Nótese que ahora tenemos dos estados finales.
En general cuando en un AFD se hace del estado inicial un estado final, no sólo se
va ha aceptar a la palabra vacı́a, puede que se acepten otras indeseables. Por ejemplo,
en el AFD,
se acepta sólo a al lenguaje a(ba)∗ y no a la palabra vacı́a. Si ponemos al estado inicial

como final obtenemos
que acepta no sólo a la palabra vacı́a , sino que se ”cuela” todo el lenguaje (ab) ∗ . Es
decir, el nuevo autómata acepta a (ab)∗ ∪ a(ba)∗ .
Ejemplo 32. A veces, el útil etiquetar los estados. Por ejemplo
Entonces se puede representar la dinámica de los estados mediante una tabla
δ a b
q0 q1 q2
q1 q2 q0
q2 q2 q2
Table 1. Tabla de transiciones
que es una forma de representar a una función δ : Q × Σ → Q, donde Q =

{q0 , q1 , q2 } el el conjunto de estados.
Formalmente, un AFD es:
Definición 23 (AFD). Un autómata finito determinista M es una 5-upla:
M = (Q, Σ, s, F, δ)
donde
(1) Q = {q0 , q1 , . . . , qn } es un conjunto finito de elementos llamados estados.
(2) Σ es un alfabeto.
(3) s ∈ Q un elemento llamado estado final.
(4) F ⊆ Q un subconjunto de estados llamados estados finales.
(5) Una función δ : Q × Σ → Q, donde δ(qi , σ) es el estado siguiente a qi .
Ejemplo 33. En el ejemplo inmediato anterior , el autómata finito determinista
es:
(1) Q = {q0 , q1 , q2 }
(2) Σ = {a, b}
(3) s = q0
(4) F = {q0 }
y δ es la función definida por la tabla 1.
Recı́procamente, dado M un AFD, M = (Q, Σ, s, F, δ), se puede construir su
diagrama de transiciones como:
(1) nodos: q ∈ Q
(2) flechas: si q ∈ Q y σ ∈ Σ, entonces se pone
Ejemplo 34. Para el autómata M = (Q, Σ, s, F, δ) con Q = {a, b}, Σ = {a, b},
s = q0 , F = {q0 } y δ definida por
δ a b
q0 q0 q1
q1 q1 q0
le corresponde diagrama de transición
Ejemplo 35. Sea M = (Q, Σ, s, F, δ) con Q = {q0 , q1 , q2 , q3 }, Σ = {a, b},

s = q0 , F = {q0 , q1 , q2 } y tabla de transiones
δ a b
q0 q0 q1
q1 q0 q2
q2 q0 q3
q3 q3 q3
luego el diagrama de transición es:
Definición 24. Sea M un AFD. El lenguaje aceptado por M es

L(M ) = {w ∈ Σ∗ | w es aceptada por M }
Ejemplo 36. Consideremos M como en el ejemplo inmediato anterior. Puede
notarse que todos los estados son de aceptación excepto uno; luego todas las pal-
abras son aceptadas excepto cuando se llega a q3 . Y la única forma de llegar a q3
es con tres b’s consecutivas:
esto es
L(M ) = {w ∈ Σ∗ | w no tiene a b3 como subpalabra}
Si σ1 , σ2 , σ3 ∈ Σ y q0 es estado inicial, el estado resultante de analizar la cadena
es, formalmente,
δ(δ(δ(q0 , σ1 ), σ2 ), σ3 )
esta aplicación se abreviará como
δ(q0 , σ1 σ2 σ3 )
más generalmente:
Definición 25. Sea qi un estado. Se definen
(1) δ(qi , ) = qi
(2) Si w ∈ Σ∗ y w = aw0 con a ∈ Σ y w0 ∈ Σ∗ , entonces
δ(q, aw0 ) = δ(δ(qi , a), w0 )
Definición 26. Sean M1 , M2 dos AFD. Se dice que M1 es equivalente a M2

si
L(M1 ) = L(M2 )
Ejemplo 37. Pongamos Σ = {a} Sea M1 el autómata finito determinista dado

por
y M2 el dado por
Es fácil ver que L(M1 ) = a∗ . También L(M2 ) = a∗ . Luego L(M1 ) = L(M2 ) y ası́
M1 es equivalente a M2
Tarea 6. (1) Obtener la expresión regular que representa el lenguaje for-

mado por todas las cadenas sobe {a, b} que tienen un número par de bes.
Construir el diagrama de transición para este lenguaje.
(2) Construir el diagrama de transición para el lenguaje dado por c ∗ (a∪bc∗ )∗ .
Convertir el diagrama en una tabla, etiquetando los estados q 0 , q1 , . . .
(3) Sea M = (Q, Σ, s, F, δ) 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
Construir el diagrama de transición. Obtener la secuencia de estados

por lo que se pasa para aceptar la cadena 110101 (el carácter del extremo
izquierdo es el primero en ser analizado).
(4) ¿ La siguiente figura es un diagrama de transición correspondiente a un
AFD? ¿Por qué o por qué no?
7. Automatas finitos no deterministas

Ejemplo 38. Diseñemos un AFD que sólo acepte a a∗ b ∪ ab∗ . Notemos que
el lenguaje a∗ b ∪ ab∗ está formada por las palabras w que tiene sufijo b o prefijo a.
Las palabras a y b deben de ser aceptadas, lo que suguiere
tabién las palabras que después de a le siguen alguna ponecia de b deben de ser
aceptadas. Por lo que añadimos
También las palabras del tipo an b con n ≥ 2 deben de ser aceptadas; se añade
7. AUTOMATAS FINITOS NO DETERMINISTAS 31
Cualesquiera otras palabras diferentes a los modelos anteriores deben de ser rec-
hazadas
Nótese que no es claro que el lenguaje a∗ b ∪ ab∗ sea exactamente el aceptado por
éste autómata. Serı́a más fácil si se permitiera:
pero éste no en un AFD sino un autómata finito no determinista.

Definición 27. Un autómata finito no determinista (AFN) es M =
(Q, Σ, s, F, ∆) donde
(1) Q = {q0 , . . . , qn } es conjunto finito de estados.
(2) |Sigma un alfabeto.

(3) s ∈ Q estado inicial.
(4) F ⊂ Q estados finales.
(5) ∆ es una relación de Q × Σ en Q, es decir,
∆ ⊆ (Q × Σ) × Q
Lo anterior significa que ∆ no es una función, pero casi lo es; queremos decir, que
si q ∈ Q y σ ∈ Σ, entonces ∆(q, σ) no es un sólo elemento, sino todo un conjunto:
∆(q, σ) ⊆ Q .
Ejemplo 39. En el autómata finito no determinista anterior (ejemplo 38) ten-

emos que
Q = {q0 , q1 , q2 , q3 , q4 }
Σ = {a, b}
s = q0
F = {q2 , q3 , q4 }
y ∆ está descrita por lo siguiente tabla:
∆ a b
q0 {q1 , q4 } {q3 }
q1 {q2 } q2
q2
q3
q4 {q4 }
Ejemplo 40. Sea M = (Q, Σ, s, F, ∆) un AFN dado por

Q = {q0 , q1 , q2 }, Σ = {a, b}
s = q0 , F = {q0 }
y relación de transición dada por
∆ a b
q0 {q1 }
q1 {q0 , q2 }
q2 {q0 }
Con estos datos se puede dibujar el diagrama de transición:
7. AUTOMATAS FINITOS NO DETERMINISTAS 33
de donde se puede ver que M acepta a (ab)∗ y también a (aba)∗ . Aún más, acepta
a ((ab)∗ (aba)∗ )∗ = (ab ∪ aba)∗ . Se puede mostrar que
L(M ) = ((ab)∗ (aba)∗ )∗
Después, basados en el lema de Arden, daremos un algoritmo para comprobar
igualdades de este tipo.
La definición formal de las palabras aceptadas es:
Definición 28. w ∈ Σ∗ es aceptada si ∆(s, w) contiene al menos un estado
de aceptación, i.e., si
∆(s, w) ∩ F 6= .
Definición 29. Sea M un AFN. El lenguaje aceptado por M es
L(M ) = {w ∈ Σ∗ | w es aceptada por M}
Las transiciones de estados pueden describirse de forma similar a los AFD con δ.
Definición 30. Sea M = (Q, Σ, s, F, ∆) un AFN.
(1) Si X ⊆ Q y σ ∈ Q se define
(
, si X =
∆(X, σ) = S
q∈X ∆(q, σ), si X 6=
(2) Si w ∈ Σ∗ con w = σw0 con σ ∈ Σ y |w0 | > 0 entonces
∆(q, w) = ∆(∆(q, σ), w 0 )
Ejemplo 41. Si Σ = {a, b};
∆(q0 , abaab) = ∆(∆(q0 , a), baab)
= ∆(∆(∆(∆(∆(q0 , a), b), a), a), b)
Ejemplo 42. Consideremos M el AFN con alfabeto Σ = {a, b} y diagrama de
transición
entonces
∆ a b
q0 {q2 }
q1 {q2 } {q2 }
q2 {q4 }
q3 {q4 } {q4 }
y ası́,
∆(q0 , ab) = ∆(∆(q0 , a), b)

= ∆({q0 , q3 }, b)
= ∆(q0 , b) ∪ ∆(q3 , b)
= {q0 , q3 } ∪
== {q0 , q3 }
que son los posibles estados que se obtienen a partir de q0 con transición ab.
Examinemos la palabra abaab:
por lo que abaab aún no se acepta. Pero
lo que nos lleva a un estado de aceptación. De aquı́ que abaab se acepta, i.e.,
abaab ∈ L(M )
8. EQUIVALENCIA ENTRE AFD Y AFN 35
Estos diagramas realmente corresponden a las siguientes ecuaciones

∆(q0 , abaab) = ∆(∆(q0 , a), baab)
= ∆({q0 , q3 }, baab)
= ∆(q0 , baab) ∪ ∆(q3 , baab)
= ∆(∆(q0 , b), aab) ∪ ∆(∆(q3 , b), aab)
= ∆({q0 , q1 }, aab) ∪ ∆( , aab)
}
| {z
= ∆(q0 , aab) ∪ ∆(q1 , aab)

= ∆(∆(q0 , a), ab) ∪ ∆(∆(q1 , a), ab)
= ∆({q0 , q3 }, ab) ∪ ∆( , ab)
= ∆(q0 , ab) ∪ ∆(q3 , ab)
= ∆(∆(q0 , a), b) ∪ ∆(∆(q3 , a), b)
= ∆({q0 , q3 }, b) ∪ ∆(q4 , b)
= {q0 , q1 } ∪ ∪ {q4 }
= {q0 , q1 , q4 }
que contiene al estado de aceptación q4 ∈ F , por lo que, como antes observamos,
abaab ∈ L(M ).
8. Equivalencia entre AFD y AFN

Lo que realmente importa de los autómatas no es su diagrama de transición, sino
el lenguaje que aceptan.
Definición 31. Sea M un AFD ó AFN, sea M 0 un AFD ó AFN. Se dice que
M es equivalente a M 0 si L(M ) = L(M 0 )
Ejemplo 43. Sea Σ = {a, b}. Sea M el autómata finito no determinista
es fácl ver que L(M ) = a(a ∪ b)∗ .

Ahora considermos M 0 el siguiente autómata finito determinista
También tenemos que L(M 0 ) = a(a ∪ b)∗ . Por lo tanto M es equivalente a M 0 .

En general, si M es un AFD, entonces es un AFN, pues δ función es en particular
una relación. Queremos probar lo recı́proco; esto es, si M es un AFN entonces existe
M 0 un AFD equivalente a M .
La idea es la siguiente: como ∆ es una relación, entonces
∆(q, σ) = {qi1 , . . . , qis }
esto es, ∆ induce una función, no de estados a estados, sino de conjuntos de estados
a conjuntos de estados:
∆0 : E × Σ → E, E ⊆ 2Q
Ejemplo 44. Sea M el AFN
Tenemos que L(M ) = a ∪ (ab)+ .

Construiremos un AFD M 0 tal que L(M 0 ) = a ∪ (ab)+ . Resulta que
∆ a b
q0 {q1 , q2 }
q1
q2 {q3 }
q3 {q2 }
La primera fila de esta tabla sugiere
donde hay nuevos estados marcados por {q0 }, {q1 , q2 } y . Necesitamos calcular
las transiciones de estos nuevos estados. Las del estado {q1 , q2 } son
∆({q1 , q2 }, a) = ∆(q1 , a) ∪ ∆(q2 , b)
= ∪ =
∆({q1 , q2 }, b) = ∆(q1 , b) ∪ ∆(q2 , b)

= ∪ {q3 } = {q3 }
Agregamos tal información en el nuevo diagrama de transición:
8. EQUIVALENCIA ENTRE AFD Y AFN 37
Las transiciones desde son hacia :

∆( , a) = , ∆( , b) = .
De nuevo, actualizamos el diagrama de transición:
Ahora necesitamos calcular las transiciones del nuevo estado {q3 }:

∆({q, 3}, a) = {q2 }, ∆(q3 , b) = {q3 }
queda ahora el diagrama
Finalmente, necesitamos las transiciones del nuevo estado {q2 }:

∆({q2 }, a) = , ∆({q2 }, b) = {q3 }
lo que completa la construcción de M 0 que es un AFD:
el cual acepta el lenguaje

L(M 0 ) = a ∪ b ∪ (ab)+ .
Nótese que los nuevos estados iniciales on aquellos que contienen a estados inicales
del autómata original.
Hemos construido un nuevo AF D M 0 = (Q0 , Σ0 , s0 , F 0 , δ 0 ) donde

Q0 = {{q0 }, , {q1 , q2 }, {q3 }, {q2 }}
Σ0 = Σ el alfabeto inicial
s0 = {s}F 0 = {{q1 , q2 }, {q3 }}
y la función de transición es
δ0 a b
{q0 } {q1 , q2 }
{q1 , q2 } {q3 }
{q3 } {q2 }
{q2 } {q3 }
Donde M 0 es equivalente a M .
Teorema 6. Sea M = (Q, Σ, s, F, ∆) un AFN. Entonces existe M 0 = (Q0 , Σ0 , s0 , F 0 , δ 0 )
un AFD equivalente a M .
Proof. Sea 2Q el conjunto potencia de Q, esto es 2Q es la colección de todos
los subconjuntos de Q. Se define M 0 como sigue:
Q0 = 2 Q
Σ0 = Σ
s0 = {s}
F 0 = {S ⊆ Q | S ∩ F 6= }
0 0 0
δ : Q × Σ → Σ, δ (S, σ) = ∆(S, σ)
Por demostrar que L(M 0 ) = L(M ). Probaremos que
w ∈ Σ∗ es aceptada por M 0 ⇔ w es aceptada por M

Una cadena w ∈ Σ∗ es aceptada por M 0 ⇔ δ 0 (s0 , w) es un estado de aceptación de
M 0 ⇔ δ(s0 , w) ∩ F 6= ⇔ ∆(s, w) ∩ F 6= ⇔ w ∈ L(M ).
Tarea 7. El las siguientes tablas, los estados iniciales están marcados con una
flecha y los estados finales con un asterisco:
(1) Convertir el siguiente AFN a AFD: Σ = {0, 1}
∆ 0 1
→ p {p, q} {p}
q {r} {r}
r {s}
∗s {s} {s}
(2) Convertir el siguiente AFN a AFD: Σ = {0, 1}
∆ 0 1
→ p {q, s} {q}
∗q {r} {q, r}
r {s} {p}
∗s {p}
(3) Convertir el siguiente AFN a AFD y describir informalmente el lenguaje
que acepta: Σ = {0, 1}:
9. -TRANSICIONES 39
∆ 0 1
→ p {p, q} {p}
q {r, s} {t}
r {p, r} {t}
∗s
∗t
Tarea 8. (1) Calcule todas las transiciones (desde el estado inicial) dadas
por las cadenas babba y aabaaaba para determinar si son aceptadas por el
autómata
a, b
a, b
a
- q - q a - qf
q0 q3 q4
b
?
qq1
b
?
qfq2
I
a, b
(2) Sea M el AFN dado por Q = {q0 , q1 }, Σ = {a, b}, s = q0 , F = {q1 } y ∆
dada por
∆ a b
q0 {q0 , q1 } {q1 }
q1 {q0 , q1 }
determinar si a2 b, ba y b2 a están en L(M ). Dibujar el diagrama de tran-
sición para M .
(3) Construir el AFD correspondiente al AFN dado por
a
a, b b
- r - re
6 b
¿qué lenguaje acepta dicho autómata?
(4) Supongamos que M es un AFN que ya es determinista. ¿Qué se obtendrá
si tratamos de convertirlo en un AFD, según el algoritmo expuesto?
9. -transiciones
Se puede extender la definición de los AFN para incluir transiciones que no depen-
dan de ninguna entrada y sin consumir ningún sı́mbolo. Tales se llaman -transiciones.
Ejemplo 45. Sea M el autómata
entonces a2 ∈ L(M ) pues

∆(q0 , a2 ) = ∆(∆(q0 , a), a)
= ∆({q0 }, a)
= ∆({q0 }, a)
= ∆(∆({q0 }, a), )
= ∆({q0 }, )
= {q1 }
Hemos usado que a2 = a2 .
Pero también a2 = aa; ası́
∆(q0 , a2 ) = ∆(q0 , aa)
= ∆(∆(q, 0, a), a)
= ∆(∆(q0 , a), a)
= ∆({q0 }, a)
= ∆(∆({q0 }, ), a)
= ∆({q1 }, a)
=
También a2 = aa ó a2 = aa, etcétera. Ası́, siempre en cualquier palabra w
se puede introducir y en su análisis de aceptación w puede no consumir, por ,
ningún sı́mbolo del alfabeto.
El precio a pagar por permitir tales -transiciones es la indefinición de los estados
siguientes. Por ejemplo, en los cáculos anteriores obtuvimos que ∆(q 0 , a2 ) = {q1 } y
también que ∆(q0 , a2 ) = . ¿Cuáles son entonces los estados siguientes? Se puede
resolver tal indefinición si se definen los estados siguientes de manera más cuidadosa.
Definición 32. Un AFN con -transiciones M es M = (Q, Σ, s, F, ∆)
donde
(1) Q es un conjunto finito (de estados).
(2) s ∈ Q estado inicial
(3) F ⊆ Q estados de aceptación
(4) ∆ es una relación de Q × (Σ ∪ {}) en Q.e
Ejemplo 46. Sea el autómata
M es un AFN con -transiciones. Nótese que se puede transitar del estado q2 a q0

sin consumir ninguna letra del alfabeto, por lo que ab es aceptada por M . Aún
más, los estados siguientes a q0 con entrada ab deben de ser {q0 , q2 }.
Se puede poner ∆ en una tabla:
9. -TRANSICIONES 41
∆ a b
q0 {q1 }
q1 {q2 }
q2 {q2 } {q0 }
Para obtener los estados siguientes a un estado dado se deben de tener en cuenta
a los estados siguientes de las -transiciones. Por ejemplo
Los estados siguientes a q0 con entrada a son

{q1 , q4 }
mientras que los estados siguentes a q1 con entrada b son {q2 , q0 , q5 }
En general, se pueden calcular los estados siguientes con lo siguiente:
Definición 33. Sea q un estado. La -cerradura de q es

(−c)(q) = {p | p es accesible desde q sin consumir ningún sı́mbolo de Σ en la entrada}
Si qi1 , . . . qin son estados se define
n
[
( − c){qi1 , . . . qin } = ( − c)(qik )
k=1
Por definición, todo estado es accesible desde sı́ mismo sin consumir ningún sı́mbolo
de entrada. Esto es,
∀q ∈ Q, q ∈ ( − c)(q)
Ejemplo 47. En el autómata
entonces
( − c)(q3 ) = {q3 }
( − c)(q0 ) = {q, q1 , q2 }, ( − c)(q4 ) = {q4 , q1 , q2 }
Definición 34. Sea q un estado y σ ∈ Σ. Se definen los estados que siguen
directamente a q pasando por σ como el conjunto
d(q, σ) = {p ∈ Q | ∃ una transciión de q a p etiquetada por σ}
y si qi1 , . . . , qik son varios estados, se define
k
[
d({qi1 , . . . , qik }, σ) = d(qij , σ)
j=1
Ejemplo 48. En el AFN del ejemplo anterior ?? tenemos que

d(q0 , a) = {q3 }, d({q3 , q4 }, b) = d(q3 , b) ∪ d(q4 , b) = {q4 , q0 }
d(q0 , b) =
Notemos que
• ( − c)(d(q, σ)) son los estados accesibles desde q tomando primero una tran-
sición sobre σ y luego tomando una o más -transiciones.
• d(( − c)(q), σ) son los estados accesibles desde q tomando una o más -
transiciones y luego una transición sobre σ.
• ( − c)(d(( − c)(q), σ)) son los estados accesibles desde q primero tamando
una o más -transiciones luego siguiendo con una transción σ y luego tomando
una o más -transiciones. Ası́:
( − c)(d(( − c)(q), σ)) son los estados siguientes a q con entrada σ.
Ejemplo 49. Para calcular los estados siguientes a q0 con entrada a,
9. -TRANSICIONES 43
primero calculamos su -cerradura:

( − c)(q0 ) = {q0 , q1 }
ensieguida los estados que siguen directamente pasando por a
d(( − c)(q0 ), a) = d(q0 , a) ∪ d(q1 , a) = {q3 , q4 }
y finalmente la -cerradura de éstos:
( − c)(d(( − c)(q0 ), a)) = ( − c)(q3 ) ∪ ( − c)(q4 )
= {q3 , q1 } ∪ {q4 , q4 }
= {q1 , q3 , q4 , q5 }
A partir de un AFN M con -transiciones se puede definir un AFN M 0 sin -transiciones
tal que L(M 0 ) = L(M ).
Ejemplo 50. Sea M el siguiente
sea ∆ su relación de transición. Vamos a definir un M 0 con relación de transición

∆0 : los estados siguientes:
• ∆0 (q0 , a) = {q1 , q3 , q4 , q5 }
• ∆0 (q0 , b) = ( − c)(d( − c)(q1 , b)); donde
( − c)(q1 ) = {q1 }, d({q1 }, b) = {q2 }, ( − c)(q2 ) = {q2 }
por lo que
∆0 (q0 , b) = {q2 }
• ∆0 (q1 , a):
( − c)(q1 ) = {q1 }
d(q1 , a) = {q4 }
( − c)(q4 ) = {q4 , q5 }
∆0 (q1 , a) = {q4 , q5 }
• ∆0 (q1 , b):
( − c)(q1 ) = {q1 }
d(q1 , b) = {q2 }
( − c){q2 } = {q2 }
∆0 (q1 , b) = {q2 }
• ∆0 (q2 , a):
( − c)(q2 ) = {q2 }
d(q2 , a) =
( − c) =
0
∆ (q2 , a) = .
0
• ∆ (q2 , b) = .
• ∆0 (q3 , a):
( − c)(q3 ) = {q3 , q1 }
d({q3 , q1 }, a) = d(q3 , a) ∪ d(q1 , a) = ∪ {q4 } = {q4 }
( − c)(q4 ) = {q4 , q5 }
∆0 (q3 , a) = {q4 , q5 }
• ∆0 (q3 , b):
( − c)(q3 ) = {q3 , q1 }
d({q3 , q1 }, b) = d(q3 , b) ∪ d(q1 , b) = {q4 } ∪ {q2 } = {q4 , q2 }
( − c){q4 , q2 } = ( − c)(q4 ) ∪ ( − c)(q2 ) = {q4 , q5 }
| {z }
∆0 (q3 , b) = {q4 , q5 }
• ∆0 (q4 , a):
( − c)(q4 ) = {q4 , q5 }
d(q4 , a) ∪ d(q5 , a) =
∆0 (q4 , a) = .
0
• ∆ (q4 , b):
( − c)(q4 ) = {q4 , q5 }
d(q4 , b) ∪ d(q5 , b) =
∆0 (q4 , b) =
• ∆0 (q5 , b) = ∆0 (q5 , a) = .
Obtenemos que M 0 es
9. -TRANSICIONES 45
Nótese que
L(M ) = {b, ab} = L(M 0 ).
Teorema 7. Sea
M = (Q, Σ, s, F, ∆)
un AFN con -transiciones. Entonces existe
M 0 = (Q0 , Σ0 , s0 , F 0 , ∆0 )
un AFN sin -transiciones tal que
L(M 0 ) = L(M ).
Proof. Se definen
Q0 = Q, Σ0 = Σ, s0 = s
F 0 = {q ∈ Q | ( − c)(q) ∩ F 6= }
y si q ∈ Q y σ ∈ Σ entonces

∆0 (q, σ) = ( − c) d(( − c)(q), σ)
Tenemos que demostrar que
w ∈ L(M 0 ) ⇔ w ∈ L(M ).
Si w ∈ L(M 0 ) entonces ∆0 (s0 , w) ∩ F 0 6= , esto es
∆0 (s, w) ∩ {q | ( − c)(q) ∩ F 6= } 6=
por lo que existe qi ∈ Q tal que
qi ∈ ∆0 (s, w) y ( − c)(qi ) ∩ F 6=
lo segundo indica que qi ∈ F o a qi le sigue un estado final después de una o más
-transiciones:
Lo que implica que w ∈ L(M ). Recı́procamente es similar.

Ejemplo 51. Sea
podemos encontrar M 0 un AFN sin -transiciones equivalente a M : por con-

strucción, los estados de M 0 son los mismos que los de M :
los estados finales de M 0 son F 0 = {q | ( − c)(q) ∩ F 6= }:

q ( − c)(q) ( − c)(q) ∩ F 6=
q0 {q0 , q1 , q2 } {q2 }
q1 {q1 , q2 } {q2 }
q2 {q2 } {q2 }
q3 {q3 }
q4 {q4 , q1 , q2 } {q2 }
de donde F 0 = {q0 , q1 , q2 , q4 }. Actualizamos nuestro diagrama de transición:
Ahora, recordemos que
∆0 (q, σ) = ( − c)(d(( − c)(q), σ))
• ∆0 (q0 , a):
( − c)(q) = {q0 , q1 , q2 }
d({q0 , q1 , q2 }, a) = d(q0 , a) ∪ d(q1 , a) ∪ d(q2 , a) = {q3 } ∪
= {q3 }
( − c)(q3 ) = {q3 }
∆0 (q0 , a) = {q3 }
9. -TRANSICIONES 47
• ∆0 (q0 , b):
( − c)(q0 ) = {q0 , q1 , q2 }
d({q0 , q1 , q2 }, b) = ∪
= ,
∆0 (q0 , b) = .
0
• ∆ (q1 , a):
( − c)(q1 ) = {q1 , q2 }
d({q1 , q2 }, a) = d(q1 , a) ∪ d(q2 , a) = ∪ = ,
∆0 (q1 , a) = .
0
• ∆ (q1 , b) = .
• ∆0 (q2 , a) = .
• ∆0 (q2 , b) = .
• ∆0 (q3 , a) :
( − c)(q3 ) = {q3 }
d(q3 , a) =
∆0 (q3 , a) = .
• ∆0 (q3 , b):
d(q3 , b) = {q4 }
( − c)(q4 ) = {q4 , q1 , q2 }
∆0 (q3 , b) = {q4 , q1 , q2 }.
0
• ∆ (q4 , a):
( − c)(q4 ) = {q4 , q1 , q2 }
d({q4 , q1 , q2 }, a) = d(q4 , a) ∪ d(q1 , a) ∪ d(q2 , a) = ∪

∆0 (q4 , a) = .
0
• ∆ (q4 , b):
d({q4 , q1 , q2 }, b) = d(q4 , b) ∪ d(q1 , b) ∪ d(q2 , b) = {q0 }
( − c)(q0 ) = {q0 , q1 , q2 }
∆0 (q4 , b) = {q0 , q1 , q2 }.
Hemos obtenido M 0 :
Tarea 9. (1) Calcular ∆(q0 , abb) y ∆(q0 , aba2 b) para el AFN siguiente
q0 q1 q2
- er a- r b- r a - rq3
6o
S
a Sb b
S ?
r S r/

q5 b q4
(2) Obtener ( − c)({q1 , q4 }) y ( − c)(d(q3 , b)) para el AFN siguiente
- q0r - qr1 - qr2f

o
S b 6
S
a S
? - S
r r
q3 b q4
(3) Usar la técnica estudiada para calcular ∆(q3 , b) en
- q0r - qr1 - qr2f

a
a
? - r? - r
r
q3 b q4
(4) Para el AFN dado en la figura siguiente
(a) obtener la tabla de transición para ∆
(b) obtener la -cerradura de qi para i = 0, 1, 2
(c) calcular ∆(q0 , a), ∆(q0 , b) y ∆(q0 , c).
a b c

- r - r - e r
q0 q1 q2
(5) Para el AFN del ejercicio inmediato anterior, obtener el AFN que se
obtiene al eliminar las -transiciones. Dar la tabla para ∆0 .
10. Autómatas finitos y expresiones regulares

Se demostrará que (teorema de Kleene):
(1) Si M es un autómata, entonces L(M ) es regular.
(2) Si L es regular, entonces existe un AF M tal que L(M ) = L.
Es decir, que los lenguajes aceptados por loa autómatas finitos son exactamente los
lenguajes regulares.
Ejemplo 52. Sea Σ = {a, b}.
(1) Construir M1 un AF N tal que L(M ) = {a}.
(2) Construir M2 un AFN tal que acepte sólo al lenguaje vacı́o.
(3) Construir un M3 un AFB tal que L(M3 ) = {}.
(4) Construir M4 un AFD tal que {a4 }.
Sol.
(1)
10. AUTÓMATAS FINITOS Y EXPRESIONES REGULARES 49
(2)
(3)
(4)
es decir
En el siguiente ejemplo se ilustra un procedimiento para construir un autómata que

acepte la unión de lenguajes.
Ejemplo 53. Sean
Construir M un AFN tal que L(M ) = L(M1 ) ∪ L(M2 ).

Sol. Tenemos que L(M1 ) = ab∗ , L(M2 ) = (ab)∗ . El M pedido es
donde claramente L(M ) = L(M1 ) ∪ L(M2 ) = ab∗ ∪ (ab)∗ .

Teorema 8. Sean M1 = (Q1 , Σ1 , s1 , F1 , ∆1 ), M2 = (Q2 , Σ2 , s2 , F2 , ∆2 ) dos
AF N . Entonces existe M un AFN tal que
L(M ) = L(M1 ) ∪ L(M2 ).
Proof. Se construirá M como un AFN con -transiciones. Sea
M = (Q, Σ, s, F, ∆)
donde
Q = Q1 ∪˙ Q2 ∪ {s}, con s 6∈ Q1 ∪ Q2
Σ = Σ ∪ Σ1
s
F0 = F1 ∪˙ F2
∆ = ∆1 ∪ ∆2 ∪ {(s, , s1 ), (s0 , , s2 )}
es decir, ∆ se define como: si σ ∈ Σ,
(
∆1 (q, σ), si q ∈ Q1
∆(q, σ) =
∆2 (q, σ), si q ∈ Q2
∆(s, σ) = , ∆(s, ) = {s1 , s2 }.
Tenemos que probar que
L(M ) = L(M1 ) ∪ L(M2 ).
∗
Sea w ∈ Σ tal que w ∈ L(M ), entonces ∆(s, w) ∩ F 6= lo que implica que
∆(s, w) ∩ F1 6= ó ∆(s, w) ∩ F2 6= .
Si ∆(s, w) ∩ F1 6= entonces
6= ∆(s, w) ∩ F1
= ∆(s, w) ∩ F1
= ∆(∆(s, ), w) ∩ F1
= ∆(s1 , w) ∩ F1
= ∆1 (s1 , w) ∩ F1
lo que implica que w ∈ L(M1 ).
Similarmente, si ∆(s, w) ∩ F2 6= entonces w ∈ L(M2 ). En cualquier caso:
w ∈ L(M1 ) ∪ L(M2 ).
Recı́procamente, L(M1 ) ⊆ L(M ) pues si w ∈ L(M1 ) entonces
6= ∆1 (s1 , w) ∩ F1
= ∆(s1 , w) ∩ F1
= ∆(∆(s, ), w) ∩ F1
= ∆(s, w) ∩ F1
= ∆(s, w) ∩ F1
⊆ ∆(s, w) ∩ F
ası́, ∆(s, w) ∩ F 6= , lo que implica w ∈ L(M ).

Similarmente L(M2 ) ⊆ L(M ); y por tanto
L(M1 ) ∪ L(M2 ) ⊆ L(M ).

Una operación que aparece para la construcción de lenguajes regulares es la unión.

Para la cual existe un algoritmo correspondiente a autómatas. La siguiente operación
que aperece con los lenguajes regulares es la concatenación. También existe un algo-
ritmo correspondiente en autómatas.
Ejemplo 54. Sean
tenemos que L(M1 ) = {a} y L(M2 ) = {b}. Encontrar M un AFN tal que L(M ) =
L(M1 )L(M2 ).
Sol.
L(M ) = {ab} = {a}{b}.
Teorema 9. Si Mi = (Qi , Σi , si , Fi , ∆i ), i = 1, 2 son dos AFN, entonces existe

un M AFN tal que
L(M ) = L(M1 )L(M2 )
Proof. Se define M = (Q, Σ, s, F, ∆) donde

Q = Q1 ∪˙ Q2
Σ = Σ 1 ∪ Σ2
s = s1
F = F2
∆ = ∆1 ∪ ∆2 ∪ (F1 × {} × {s1 })
es decir, si σ ∈ Σ1 ∪ Σ2 , q ∈ Q1 ∪ Q2 ,

∆1 (q, σ)
 si q ∈ Q1 y σ ∈ Σ1
∆(q, σ) = ∆2 (q, σ) si q ∈ Q2 y σ ∈ Σ2


otro caso.
(
{s2 } si q ∈ F1
∆(q, ) =
si q ∈
6 F2 .
Por demostrar que
L(M ) = L(M1 )L(M2 )
∗
es decir, que para w ∈ Σ ,
w ∈ L(M ) ⇔ w ∈ L(M1 )L(M2 ).
(⇐) Si w ∈ L(M1 )L(M2 ) entonces w = xy con x ∈ L(M1 ) y y ∈ L(M2 ); en
particular x ∈ Σ∗1 y y ∈ Σ∗2 . Podemos escribir
w = xy
luego
(4) ∆(s, w) = ∆(∆(∆(s, x), ), y).
Como x ∈ Σ∗1 , entonces
∆(s, x) = ∆(s1 , x)
= ∆1 (s1 , x)
y como x ∈ L(M1 ) entonces ∆(s1 , x) ∩ F1 6= , por lo que
∆1 (s1 , x) = {. . . , q , . . .}
|{z}
∈F1
y
∆(∆(s, x), ) = ∆({. . . , q, . . .}, )
= ∆( q , )
|{z}
∈F1
= {s2 }
Usando la ecuación (4),
∆(s, w) = ∆(s2 , y)
= ∆(s2 , y)
pues y ∈ Σ∗2 . Pero ∆2 (s2 , y) ∩ F2 6= , luego
∆(s, w) ∩ F = ∆(s, w) ∩ F2 6=
Figure 2. M
lo que implica que

w ∈ L(M ).
(⇒) Supongamos que w ∈ L(M ) entonces
∆(s, w) ∩F 6=
| {z }
∆(s1 ,w)
es decir, las transiciones indicadas por w deben de pasar del estado s1 en

M1 a un estado de aceptación en M2 : la única forma de pasar de M1 a
M2 es usando las -transiciones que ligan a los estados finales de M1 con
el inicial de M1 (ver figura 2). Por lo que w debe primero de transitar
hacia los estados de F1 y luego hacia F2 . Esto es
w = xy
con ∆1 (s1 , x) ∩ F1 6= y ∆2 (s2 , y) ∩ F2 6= . Es decir x ∈ L(M1 ) y
y ∈ L(M2 ). Por lo tanto
w = xy ∈ L(M1 )L(M2 )

La siguiente operación que se usa para la construcción de los lenguajes regulares
es la cerradure de Kleene. También existe una construcción similar para autómatas.
Ejemplo 55. En cada inciso considere L(M ) y construya M1 un AFN tal que
L(M1 ) = L(M )∗ .
(1)
(2)
Sol.
(1) Tenemos que L(M ) = {a}. Por lo que tenemos que construir M1 tal que
L(M1 ) = a∗ . Tal M1 es:
(2) Tenemos que L(M ) = {ab, ac}. Queremos M1 un AFN tal que L(M1 ) =
(ab ∪ ac)∗ . Tal es
El ejemplo anterior ilustra el algoritmo subyacente en la demostración del siguiente

teorema.
Teorema 10. Si M = (Q, Σ, s, F, ∆) es un AFN, entonces existe M1 =
(Q1 , Σ1 , s1 , F1 , ∆1 ) tal que L(M1 ) = L(M )∗ .
Proof. Se le añade un nuevo estado a M :
Q1 = Q ∪ {s1 } con s1 6∈ Q1
Σ1 = Σ
s1
F1 = {s1 }
∆ se le añaden -transiciones de los estados finales a s0 :
Si σ ∈ Σ1 , q ∈ Q1 : (
∆(q, σ) si q ∈ Q
∆1 (q, σ) =
otro caso.

{s1 }
 si q ∈ F
∆(q, ) = {s} si q = s1


otro caso.
Tenemos que demostrar que
w ∈ L(M1 ) ⇔ w ∈ L(M )∗ .

Hemos demostrado:
Teorema 11. Los lenguajes aceptados por los automatas finitos contienen a
(1) , {}, los lenguajes unitarios {a}, ∀a ∈ Σ.
(2) Además tales elnguajes son cerrados con respecto a la unión, concate-
nación y cerradura de Kleene.
Corolario 1. Si r es una expresión regular entonces existe M un autómata
finito tal que r = L(M ).
Proof. Las expresiones regulares se contruyen a partir de , {} y los lengua-
jes unitarios {σ}, σ ∈ Σ con cerrauras uniones y concatenaciones; y para tales
construcciones existen autómatas que las aceptan.

Tarea 10.
(1) Obtener un AFN que acepte .
(2) Obtener un AFN que acepte {a}. Obtener otro AFN que acepte {b}. Usar
las técnicas vistas para unir éstos AFN en uno que acepte el lenguaje
{a, b}.
(3) Obtener un AFN que acepte (a ∪ b)∗ ∪ (aba)+ .
(4) Obtener un AFN que acepte todas las cadenas de la forma bow, bowwowwow,
bowwowwowwowwow, . . .. Conseguir un AFN que acepte todas las cade-
nas de la forma ohmy, ohmyohmy, ohmyohmyohmy, . . .. Unir los dos
AFN para que se acepte la uninión de los dos lenguajes. Téngase en
cuenta que los sı́mbolos de un alfabeto no tiene por qué ser caracteres de
longitud uno.
(5) Sea M1 dado por
b
- r ? - re
q1 a q2
b
? a - rfq
r
d 4
q3
6
b
y M2 dado por
a
- ?
r - r - rf
p1 a p2 b p3
Obtener un AFN que acepte L(M1 )L(M2 ). Obtener un AFN que acepte
L(M2 )L(M1 ).
(6) Sean M1 = {q1 , q2 , q3 }, a, b, q1 , {q1 }, ∆1 y M2 = {p1 , p2 , p3 , p4 }, {0, 1}, p1, {p1 , p2 }, ∆2 ,
donde ∆1 y ∆2 viene dados por las tablas siguientes:
∆2 0 1
∆1 a b
p1 {p2 } {p3 , p4 }
q1 {q2 , q3 }
p2 {p3 , p4 }
q2 {q1 }
p3 {p2 }
q3 {q3 } {q3 }
p4 {p3 }
Obtener un AFN que acepte L(M1 )L(M2 ). Obtener un AFN que acepte
L(M2 )L(M1 )L(M1 ). Obtener finalmente, un AFN que acepte L(M1 )2 ∪
L(M1 ).
(7) Obtener una AFN para (ab)∗ a partir de los AFN que aceptan {a} y {b}.
(8) Obtener un AFN para (aa ∪ b)∗ (bb ∪ a)∗ a partir de los AFN que aceptan
{a} y {b}.
(9) Obtener un AFN para
((a ∪ b)(a ∪ b))∗ ∪ ((a ∪ b)(a ∪ b)(a ∪ b))∗
a partir de los AFN para {a} y {b}.
(10) Si M = (Q, Σ, s, F, δ) es un autómata finito determinista, entonces el
complemento de L(M ) [es decir Σ∗ − L(M )] es aceptado por el autómata
M 0 = (Q, Σ, s, Q − F, δ). ¿Es M 0 un AFD o un AFN? Obtener un AFD
que acepte ab∗ ab. Obtener un autómata finito que acepte {a, b}∗ − ab∗ ab.
11. Lema de Arden

Definición 35. Sea M = (Q, Σ, s, F, ∆) un AFN con estado inicial s = q0 .
Sea qi ∈ Q. Se define
Ai = {w ∈ Σ∗ |, ∆(qi , w ∩ F 6= }
i.e., Ai es el conjunto de cadenas que desde qi llegan a un estado de aceptación. El
conjunto Ai se llama cadenas aceptadas por el estado qi .
Notemos que
• A0 = L(M )
• Si qi ∈ F , entonces ∈ Ai .
Ejemplo 56. En el AFN siguiente
tenemos que
A5 = , A4 = {}, A3 = {a}
A2 = { }, A1 = {b}, A0 = {ba, ab}.
Si qj ∈ ∆(qi , σ) entonces σAj ⊂ Ai , pues, si w ∈ σAj entonces w = σx para
algún x ∈ Aj , esto es ∆(qj , x) ∩ F 6= . Luego
∆(qi , w) ∩ F = Delta(∆(qi , sigma), x) ∩ F

⊇ ∆(qj , x) ∩ F
11. LEMA DE ARDEN 57
Por lo que
[
(5) Ai = {σAj | qj ∈ ∆(qi , σ)}
σ
Ejemplo 57. En el AFN del ejemplo anterior 47, usando la ecuación (5)
A0 = aA1 ∪ bA3 , A1 = bA2 ∪ aA5 , A3 = aA4 ∪ bA5
A2 = aA5 ∪ bA5 ∪ , A4 = ∪ aA5 ∪ bA5
A5 =
este es un sistema de cuaciones que se puede resolver por sustitución regresiva:
A4 = , A3 = a, A2 = , A1 = b
L(M ) = A0 = ab ∪ ba
es decir, hemos calculado L(M ) = ab ∪ ba.
A veces, resultan ecuaciones autorecursivas. Por ejemplo, en
resula, usando de nuevo la ecuación (5),

A0 = aA0 ∪ bA1 , A1 =
A0 = aA0 ∪ b
para resolver tales ecuaciones autorecursivas se usa el lema de Arden.
Lema 3 (de Arden). Una ecuación de la forma
(6) X = AX ∪ B
donde 6∈ A tiene como solución única a
X = A∗ B
Proof.
(1) Primero notemos que X = A∗ B es solución de (6), pues
A∗ B = (A+ ∪ )B
= A+ B ∪ B
= AA∗ B ∪ B
= A(A∗ B) ∪ B
(2) Ahora supongamos que hay otra solución a (6) y llamémosla Y . Esto es
Y = AY ∪ B
∗
con X = A B 6= Y . Entonces
X ∪ Y = AX ∪ B ∪ AY ∪ B
= A(X ∪ Y ) ∪ B
esto es S = X ∪ Y es también solución y es más grande que X, pues
X ⊂ S. Podemos escribir
S = A∗ B ∪ C
donde C = S − A∗ B 6= y A∗ B ∩ C = .
Luego, como S es solución.

S = AS ∪ B
y
A∗ ∪ C = AA∗ B ∪ AC ∪ B
= A+ B ∪ AC ∪ B
= (A+ ∪ )B ∪ AC
= A∗ B ∪ AC
por lo que
(A∗ B ∪ C) ∩ C = (A∗ B ∪ AC) ∩ C
= (A∗ B ∩ C) ∪ (AC ∩ C)
= ∪ AC ∪ C
y entonces
C = AC ∩ C ⊆ AC
es decir
C ⊆ AC
Sea w ∈ C tal que |w| es mı́nima; entonces w = aw0 con a ∈ A y |a| > 0
pues 6∈ A. Luego
|w| = |a| + |w0 | > |w0 |
|w| > |w0 |
lo cual es imposible, pues |w| es mı́nima.
Por lo tanto X = A∗ B es la solución única.

Ejemplo 58. Consideremos M como
entonces
A0 = aA0 ∪ bA1
A1 =
A0 = aA0 ∪ b
∗
y como 6∈ {a}, entonces A0 = a b. Es decir
L(M ) = a∗ b.
Ejemplo 59. En M el AFN siguiente, calcule L(M ).
Proof.
A0 = aA1 ∪
A1 = cA2 ∪ bA3
A2 = A0
A3 = A0
A1 = cA0 ∪ bA0
= cA0 ∪ bA0
= (c ∪ b)A0
y
A0 = a(c ∪ b)A0 ∪
y como 6∈ L(a(c ∪ b)) entonces podemos usar el lema de Arden y obtener
A0 = (a(c ∪ b))∗ = (ac ∪ bc)∗

Ejemplo 60. Calcule el lenguaje aceptado por el siguiente autómata.
Sol. Tenemos que

A0 = aA1
A1 = aA2 ∪ bA4
A2 = aA3 ∪ bA4
A3 = ∪ aA3 ∪ bA4
A4 = ∪ bA4 = bA4 ∪
entonces, por el lema de Areden, como 6∈ {b},
A4 = b ∗ = b ∗
A3 = aA3 ∪ ( ∪ bb∗ )
= aA3 ∪ b∗
lo que implica,
A3 = a ∗ b∗
y
A2 = = aa∗ b∗ ∪ bb∗
= a + b∗ ∪ b +
A1 = aa+ b∗ ∪ ab∗ ∪ bb∗

por lo tanto,
A0 = a2 a+ ∪ a2 b∗ ∪ ab+

El lema de Arden garantiza que
Lema 4. Sea M un AF. Existe r una expresión regular tal que
L(M ) = L(r).
y en consecuencia,
Teorema 12 (Kleen). Un lenguaje L es regular si y sólo si L es aceptado por
algún autómata.
Tarea 11.
(1) Obtener un AFN para (aa ∪ b)∗ (bb ∪ a)∗ a partir de los AFN que aceptan
{a} y {b}.
(2) Obtener un AFN para
((a ∪ b)(a ∪ b))∗ ∪ ((a ∪ b)(a ∪ b)(a ∪ b))∗
a partir de los AFN para {a} y {b}.
(3) Si M = (Q, Σ, s, F, δ) es un autómata finito determinista, entonces el
complemento de L(M ) [es decir Σ∗ − L(M )] es aceptado por el autómata
M 0 = (Q, Σ, s, Q − F, δ). ¿Es M 0 un AFD o un AFN? Obtener un AFD
que acepte ab∗ ab. Obtener un autómata finito que acepte {a, b}∗ − ab∗ ab.
(4) Obtener una expresión regular para el lenguaje aceptado por el autómata
finito siguiente:
- r a - r a - r a - r a - rf
Qb Qb Q b 6
Q Q Q
sQ s
Q b sQ
r b - r - r
Q Q a 6
Qa Q a
sQ r a sQ r
-
Q
bQ b
Q ?
s rg
(5) Obtener una expresión regular para el AFD siguiente:

a
- ? r a - rf
b@
R
@ r b
I
a, b
(6) Obtener una expresión regular para los lenguajes aceptados por cada uno
de los autómatas siguientes:
(a)
a, b q a
-q1 r - r2f - rq3
I 6
b a, b
(b)
a
/
- si
q1
a >
Z
Zb b
Z
~
Z
q2 s b - s q3
6
a
(c)
- r
q1
b a
> @ a
b
@
?
rg a -R@
g
r
q2 q3
I
b
(d)
b
- r?
q 1 q
- r2 - rq3 a- qr4 a rf a, b
-
a b q5
I I 6
b a b
(e)
- qr1 a - q2r b - re a, b
q3
b a
?
q4 r b
K
A
a
12. Propiedades de los lenguajes regulares
12.1. Lema del bombeo. El lema del bombeo permite mostrar que no todos
los lenguajes son regulares.
Lema 5 (del bombeo). Sea L un lenguaje regular. Entonces existe n constante
tal que ∀w ∈ L con |w| ≥ n se obtiene que
w = uvx con |v| ≥ 1 y |uv| ≤ n
y además
∀i, uv i x ∈ L.
Proof. Si L es finito entonces existe m la mayor de las longitudes de las
palabras de L. Se pone n = m + 1 y el lema se cumple por vacuidad (no hay
palabras, en L, de longitud ≥ n).
Si L es infinito, entonces, por el teorema de Kleene, existe M un AFD tal que
L = L(M ). Sea
M = (Q, Σ, s, F, δ).
Definimos n = |Q| el número de estados de M . Si w ∈ L con |w| ≥ n entonces
w = a1 · · · a|w|−1 a|w|
con cada ai ∈ Σ. Definimos además q1 , q2 , . . . , q|w| como los estados que resultan
de las transiciones indicadas por w, esto es:
q1 = δ(s, a1 ), q2 = δ(q1 , a2 ), . . . , q|w| = δ(q|w|−1 , a|w| ).
Puesto que w ∈ L(M ) entonces q|w| ∈ F :
Como sólo hay n estados, los estados s, q1 , . . . , qn , . . . , q|w| no pueden ser todos
diferentes, pues en tal caso tendrı́amos |w| + 1 > n: más estados que n!. Por lo que
algunos de éstos se repiten: existen j, k tales que 1 ≤ j < k ≤ n ≤ |w| tales que
qj = qk . Lo que obliga la aparición de un ciclo:
Definimos
12. PROPIEDADES DE LOS LENGUAJES REGULARES 63
• u = a 1 · · · aj
• v = aj+1 · · · ak
• x = ak+1 · · · a| w|
Entonces
w = uvx
Como v corresponde al ciclo, y este existe entonces |v| > 1. Además
|uv| = k ≤ n.
Finalmente notemos que u lleva el estado inicial sl estado que se repite qj , luego x
continua con este estado hasta lllevarlo al estdoo de aceptación q|w| ;
δ(s, ux) = δ(δ(s, u), x)
= δ(qj , u)
= δ(qk , x)
= q|w| ∈ F
por lo que ux ∈ L. Similarmente, como v 2 lleva el estado qj al estado
qk
entonces uv 2 x también se acepta. En general, si i ≥ 0 entonce
δ(s, uv i x) = δ(δ(δ(s, u), v i ), x)
= δ(δ(qj , v i ), x)
= δ(qk , x))
= q|w| ∈ F,
por lo que uv i x ∈ F .

Ejemplo 61. Sea Σ = {0, 1} y L el lenguaje de todas las cadenas con el mismo
númoer de 0’s que de 1’s. Demostrar que L no es regular.
Proof. Por contradicción: si L fuera regular entonces existe n tal que se
cumple el lema del bombeo. Esto es las palabras de longitud más grande o igual
a n se descomponen en tres partes con ciertas caracterı́sticas. En particular q =
0n 1n ∈ L es una palabra de longitud |w| = 2n > n, luego tal se puede descomponer
en tres partes u, v, x tales que
w = 0n 1n = uvx
con |uv| ≤ n, |v| > 1 y uv i x ∈ L, ∀i ≥ 0. Como uv es la parte al principio de 0n 1n
y |uv| ≤ n entonces uv está formada sólo por ceros, por lo que x, que ess la parte
final de w, debe de tener todos los unos:
w=0
| ·{z
· · 0} |0 · · · 01
{z · · · 1}
uv x
Pero para i = 0, ux ∈ L, por lo que ux tiene n unos, de donde debe de tener n

ceros que son los de u. Se deduce entonces que v no contribuye con ningún cero a

w = uvx. Esto es v = , lo cual contradice el elma del bombeo. Por lo tanto L no
es regular.
Ejemplo 62. Sea 2

L = {ai | i ≥ 1}
entonces L no es un lenguaje regular.
Proof. Supongamos que L es regular. Existe una constante n tal que cualquier
palabra w ∈ L con |w| ≥ n se descompone según las caracterı́sticas del lema del
bombeo.
2 2
Por definición de L tenemos que an ∈ L. Luego an se puede decomponer
como 2
an = uvx
con |uv| ≤ n y uv i x ∈ L, ∀i ≥ 0.. En particular uv 2 x ∈ L. Por lo que, para algún
k entero |uv 2 x| = k 2 . Luego,
2
n2 = |an |
= |uvx|
< |uv 2 x|
= |u| + |v| + |v| + |x|
= |uvx| + |v|
≤ n2 + n
pues n ≥ |uv| ≥ |v|, Se sigue que
n2 < |uv 2 x| ≤ n2 + n
< n2 + 2n + 1
= (n + 1)2
entonces
n2 < |uv 2 x| < (n + 1)2
| {z }
2 2 2
k2
estp es, n < k < (n + 1) , i.e., n < k < n + 1 con k entero: un absurdo.

Tarea 12.
(1) Probar que el lenguaje
L = {ap | p es primo}
no es regular. item Dewterminar si los siguientes lenguajes son regulares
y decir o probar por qué si o por qué no.
(a) {ai b2i | i ≥ 1}
i
(b) (ab | i ≥ i
2n
(c) {a | n ≥ 0}
n
(d) {a2 | n ≥ 0}
CHAPTER 2
Lenguajes Independientes del Contexto
1. Gramáticas regulares
Un autómata finito puede considerarse como un generador de lenguajes: si M es
un AF entonces genera a L(M ). Por ejemplo, consideremos
es tal que
L(M ) = a(a∗ ∪ b∗ )b
Las cadenas aceptadas por M se empiezan a producir como:
S → aE
(la flecha se leeerá ”produce”), donde S es un sı́mbolo lallamdo inicial y E es un

sı́mbolo llamado ”no terminal”. A su vez, el sı́mbolo E tiene dos posibilidades subse-
cuentes:
E→A
ó
E→B
dependiente de la -transición hacia q3 ó q4 , donde A y B son también sı́mbolos no

terminales. Si A indica el camino superior, tenemos
A → aA
ó
A→b
65
66 2. LENGUAJES INDEPENDIENTES DEL CONTEXTO
donde ahora b es un sı́mbolo terminal. Similarmente, para el camino inferior,
B → bB
ó
B→b
En resumen, tenemos
S → aE
E→A
E→B
A → aA
A→b
B → bB
B→b
En forma más compacta, si ”—”=”∨”:

(1) S → aE
(2) E → A|B
(3) A → aA | b
(4) B → bB | b
las anteriores se consideran regas de substitución para la generación de cadenas.
Por ejemplo: tomemos S:
S
la substituimos por aE:
aE
luego substituimos A por E (también pudimos haber substituido E por B):
aA
luego substituimos A por aA:

aaA
y luego A por b:
aab
Todo este proceso de substituciones se puede abreviar como
(1)
S ⇒ aE
(2)
⇒ aA
(3)
aaA
(3)
aab
El sı́mbolo ”⇒”se lee ”deriva”.

1. GRAMÁTICAS REGULARES 67
También la cadena a3 b se puede generar como

(2)
S ⇒ aE
(2)
⇒ aA
(3)
⇒ aaA
(3)
⇒ aaaA
(3)
⇒ aaab
∗
Definición 36. Si w ∈ Σ∗ , se usa S ⇒ w para indicar que w se generó a
partir de S en cero o más etapas.
∗ ∗
Ejemplo 63. S ⇒ a2 b, S ⇒ a3 b.
En las producciones hay sı́mbolos de un alfabeto Σ. Tales se llaman terminales
para indicar que no son suceptibles a ser susbstituidos. Los sı́mbolos que sı́ pueden
serlo se llaman no terminales. El sı́mbolo inicial S es siempre no terminal.
La generación de cadenas se hace de izuierda a derecha, por lo que en las produc-
ciones, los sı́mbolos no terminales deben de aparecer a la derecha.
Definición 37. En la producción
A→γ
A se llama cabeza de la producción y γ se llama cuerpo de la producción.
Definición 38. Una gramática regular es una 4-tupla,
G = (Σ, N, S, P )
donde
• Σ es un alfabeto
• N un conjunto finito de sı́mbolos no terminales
• S ∈ N llamado sı́mbolo inicial
• P es una colleción de reglas de substitución llamadas poducciones que
son de la forma
A→γ
con A ∈ N y γ ∈ (Σ ∪ N )∗ tal que
(1) u tiene un no terminal como máximo
(2) si γ contiene un no terminal, este está en el exremo derecho.
Se pude decir que en la producción A → γ, γ ∈ Σ∗ (N ∪ )∗ con terminal.
Definición 39. El lenguaje generado por G se denota por L(G) y este es
∗
L(G) = {w ∈ Σ∗ | S ⇒ w}
Ejemplo 64. Sea G = (Σ, N, S, P ) gramática regular donde
Σ = {a, b}, N = {S, A}
y las producciones son

P : S → bA
A → aaA | b |
entonces
S ⇒ bA
⇒ baa
⇒ baab
por lo que baab ∈ L(G). También,
S ⇒ bA
⇒ baaA
⇒ baaaaA
⇒ baaaab
2
, b(aa) b ∈ L(G). En general,
S ⇒ bA
⇒ baaA
⇒ b(aa)2 A
..
.
⇒ b(aa)n A
⇒ b(aa)n b
por lo que
∀n ≥ 1, ba2n b = b(aa)n b ∈ L(G).
También
S ⇒ bA
⇒ baaA
⇒ b(aa)2 A
..
.
⇒ b(aa)n A
⇒ b(aa)n = b(aa)n = ba2n ∈ L(G).
Nótese que
S ⇒ bA
⇒ b = b ∈ L(G)
y
S ⇒ bA
⇒ bb = b2 ∈ L(G)
por lo que
b(a2 )∗ ( ∪ b) = b(a2 )∗ ∪ b(a2 )∗ b ⊆ L(G)
2. GRAMÁTICAS REGULARES Y LENGUAJES REGULARES 69
Recı́procamente L(G) ⊆ b(a2 )∗ ( ∪ b), porque si w ∈ L(G),

S ⇒ bA ⇒ · · · ⇒ w1 ⇒ w
onde las primeras derivaciones S ⇒ bA ⇒ · · · ⇒ w1 ninguna de ellas proviene
de aplicar A → by/ó A → . Es decir, éstas derivaciones resultan de aplicar la
producción A → aaA. Por lo que
w1 = b(aa)k−1 A
donde k es el número de deriaciojes aplicadas. Luego,
S ⇒ bA ⇒ · · · ⇒ b(aa)k−1 A ⇒ w
donde la última derivación es de A → b ó A. Se deduce que
w = b(aa)k−1 b ’o w = b(aa)k−1.
Ası́ w ∈ b(a2 )∗ b ∪ b(a2 )∗ .
Las producciones son pares: en el ejemplo anterior
P = {(S, bA), (A, aaA), (A, b), (A, )}.
Únicamente los sı́mbolos no terminales se escriben con mayúsculas, ası́ una gra-
matica regular queda descrita completamente por sus producciones. Por ejemplo
S → aS | b
describre a la gramática regular que genera al lenguaje a ∗ b.
2. Gramáticas regulares y lenguajes regulares

Supongamos que L es un lenguaje regular. Se puede obtener una gramática regular
que genera L. Para esto será útil M un AFD tal que L = L(M ).
Supongamos que M = (Q, Σ, s, F, δ). Se define G = (N, Σ, S, P ) mediante
N = Q, Σ = Σ, S = s
(
q → ap si δ(q, a) = p
P : ∀q ∈ Q,
q→ si q ∈ F
Ejemplo 65. L = a∗ b es un lenguaje regular. Un AFD que acepta L es
Una gramática que aceptará a L = a∗ b es

q0 → aq0 | bq1
q1 → | aq2 | bq2
q2 → aq2 | bq2
donde q0 , q1 , q2 son no terminales. En efecto, tenemos el siguiente teorema general
Teorema 13. Si M es un AFD y G la gramática descrita anteriormente,
entonces
L(M ) = L(G).
Proof. Si w ∈ L(M ) entonces w = σ1 · · · σn con cada σi ∈ Σ. Ası́ δ(s, σ1 · · · σn ) =

p ∈ F . Pongamos s = q0 y
δ(q0 , σ1 ) = q1
δ(q1 , σ2 ) = q2
..
.
δ(qn−2 , σn−1 ) = qn−1
δ(qn−1 , σn ) = qn = p
eso es:
Los anteriores inducen las siguientes producciones en G:
0) q0 → σ1 q1
1) q1 → σ2 q2
..
.
n − 2) qn−2 → σn−1 qn−1
n − 1) qn−1 → σn qn
n) p = qn →
luego
(0)
s ⇒ σ1 q1
(1)
⇒ σ 1 σ2 q 2
(2)
⇒ σ 1 σ2 σ3 q 3
..
.
(n−1
⇒ σ 1 σ2 · · · σ n q n
(n)
⇒ σ 1 σ2 · · · σ n = σ 1 σ2 · · · σ n
lo que implica que w = σ1 σ2 , · · · σn es generada por G, i.e., w ∈ L(G). Hemos

demostrado
L(M ) ⊆ L(G).
Recı́procamente, supongamos w ∈ L(G) entoncea w fué derivada como

s = q 0 ⇒ σ1 q1
⇒ σ 1 σ2 q 2
⇒ σ 1 σ2 σ3 q 3
..
.
σ1 · · · σ n q n
σ1 · · · σ n = σ 1 · · · σ n = w
luego
δ(s, w) = δ(s, σ1 · · · σn )
= δ(δ(s, σ1 ), σ2 · · · σn )
= δ(q1 , σ2 · · · σn ) pues s → σ1 q1 ⇔ δ(s, σ1 ) = q1
= δ(δ(q1 , σ2 ), σ3 · · · σn ) pues q1 → σ2 q2 ⇔ δ(q1 , σ2 ) = q2
= δ(qn−1 , σn )
= qn ∈ F pues qn → sólo es posible con qn ∈ F.
Por tanto w ∈ L(M ). Hemos demostrado
L(G) ⊆ L(M ).

El teorema recı́proco también es cierto.
Teorema 14. Sea G una gramática regular. Entonces existe M un AFN tal
que
L(M ) = L(G).
Proof. Sea G = (N, Σ, S, P ) una gramática regular. Se define M un AFN tal
que
M = (Q, Σ, s, F, ∆)
con
s = S, F = {f } donde f 6∈ Σ, f 6∈ N
Los estados Q ⊇ N ∪ {f } y falta añadir estados a Q lo cual haremos en la
definición de ∆:
(1) Si A → σ1 · · · σn B es produccción de G con A, B no terminales, entonces
se añaden estados q1 , . . . , qn−1 a Q y se define
∆(A, σ1 ) = q1 , ∆(q1 , σ2 ) = q2 , . . . , ∆(qn−1 , σn ) = B,
esto es, la producción A → σ1 · · · , σn B en G se transforma en
σ σ n σ
A →1 q1 →2 q2 → · · · → qn−1 → B
(2) Si A → σ1 · · · σn (cadena de terminales) entonces se añaden los estados
r1 , r2 , . . . , rn−1 a Q y se define en el autómata M ,
σ σ n σ
A →1 r1 →2 r2 → · · · → rn−1 → f
Por ejemplo, si G es la gramática regular

S → aB | bA |
A → abaS
B → babS
da lugar al autómata
Ası́ L(M ) = L(G) pues si w ∈ L(G) entones w debe ser generada por derivaciones:
S ⇒ α 1 A1 con α1 ∈ Σ∗ y A1 no terminal
⇒ α 1 α2 A 2 con α2 ∈ Σ∗ y A→ α2 A2 en G
..
.
⇒ α1 · · · αn−1 An−1 con an ∈ Σ∗ y αn ∈ Σ∗
que en el AF N , ésta construcción queda como

→s →
| ·{z
· · →} A1 |→ ·{z
· · →} A2 → · · · → An−1 →
| ·{z
· · →} f ∈F
letras que forman α1 letras que forman α2 letras que forman αn
∗
s ⇒ w, por lo que w ∈ L(G).

Recı́procamente, si w ∈ L(M ), entonces siguiendo el razonamiento anterior
Tenemos
Corolario 2. L es lenguaje regular ⇔ L es generado por una gramática reg-

ular.
Tarea 13. (1) Supongamos que tenemos las reglas S → aS|bT y T → aa.
Dar una derivación para abaa, aabaa, aaabaa. Probar que se pueden
derivar ak ba2 para k ≥ 1. ¿Es posible derivar las cadenas baa, b o aa?
(2) Obtener una gramática regular que genere los siguientes lenguajes
(a) a∗ b ∪ a
(b) a∗ b ∪ b∗ a
(c) (a∗ b ∪ b∗ a)∗
(3) La gramática regular dada por
S → bA|aB|
A → abaS
B → babS
genera un lenguaje regular. Obtener una expresión regular para este lenguaje.
(4) En nuestra definición de gramáticas regulares de dijo que si en el extremo
derecho de una producción hay un no terminal, éste debe de estar situado
en el extremo derecho. Esto corresponde a la generación de cadenas de
izquierda a derecha. Por esta razón, una gramática regular también puede
llamarse gramática regular por la derecha. Una gramática regular por la
izquierda es aquella cuyas cadenas son generadas por la derecha, es decir
sus porducciones son pares de N × (N ∪ Σ)Σ∗ .
(1) Obtener una gramática regular por la izquierda para el lenguaje {a n baa | n ≥
0}.
(2) Obtener las gramáticas regulares por la derecha y la izquierda para
{w ∈ {a, b, c}∗ | w termina en b y toda c va seguida de una a }
(3) Para toda gramática G = (N, σ, S, P ) que sea regular (por la izquierda o
por la derecha), se puede definir la inversa de G como GI = (N, Σ, S, P 0 )
donde
P 0 = {(A, xI ) | (A, x) ∈ P }.
Por lo tanto, si A → aB es una producción de G, entonces, A → Ba es

una producción de GI .
Supongamos que G es una gramática regular por la derecha.
(a) Probar que GI es una gramática regular por la izquierda.
(b) Probar que w ∈ L(G) si y sólo si w I ∈ L(G0 ) por inducción sobre el
número de producciones usadas para obtener w.
Se puede deducir de la parte (c) que la clase de los lenguajes generados por
gramáticas regulares por la izquierda es la misma que la clase de lenguajes
generados por gramáticas gegulares por la derecha. Por eso habitualmente,
el término gramática regular se aplica para referirse a cualquier gramática
ya sea regular por la izquierda o regular por la derecha.
(4) Construir la gramática regular para el lenguaje aceptado por el autómata
finito siguiente:
a
- q?
d - q - q
a b
b I b
?
q ?
b q
a
?
q
a@R
@
q
(5) Construir un autómata finito para la gramática regular

S → abA|B|baB|
A → bS|b
B → aS
(6) Obtener una gramática regular para el lenguaje
L = {w ∈ {a, b}∗ | w no contiene la subcadena aa}
(7) Obtener una gramática regular para L = {an bn | n ≥ 0}.
3. Gramáticas independientes del contexto

Recordemos que en una gramática regular G, las producciones son parejas:

A → wB

P : ó


A→w
con A, B no terminales y w ∈ Σ∗ cadena de terminales. Éstas corresponden a las

parejas:
(A, wB) ó (A, w)
ası́
P ⊆ N × Σ∗ (N ∪ {})
esto es, en las producciones, los terminales, si aparecen, tienen que estar en el extremo
derecho del cuerpo de la producción.
Si se permiten que los terminales aparezcan, más de una vez, y en cualquier lado,
i.e.,
P ⊆ N × (N ∪ Σ)∗
entonces se obtienen gramáticas independientes del contexto.
Ejemplo 66. La gramática
S → aB | bA
A → a | aS | bAA
B → b | bS | aBB
es una gramática independiente del contexto que no es regular.
Definición 40. Una gramática independiente del contexto (GIC) es una
4-tupla
G = (N, |sigma, S, P )
donde
• N es colección de sı́mbolos no terminales
• Σ es un alfabeto
• S ∈ N sı́mbolo inicial
• P ⊆ N |times(N ∪ Σ)∗ conjunto de producciones.
El lenguaje que genera G, L(G) se llama lenguaje independiente del contexto:
∗
L(G) = {w ∈ Σ∗ | S ⇒ w}.
3. GRAMÁTICAS INDEPENDIENTES DEL CONTEXTO 75
Ejemplo 67. Consideremos como G la grámatica independiente del contexto

(que no es regular) siguiente:
S → aSb | .
entonces
S⇒
i.e., ∈ L(G). Además
S ⇒ aSb
⇒ ab = ab
i.e., ab ∈ L(G). También
S ⇒ aSb
⇒ aaSbb
⇒ aabb = a2 b2
i.e., a2 b2 ∈ L(G). En general
{an bb | n ≥ 0} ⊆ L(G).
Recı́procamente, si w ∈ L(G), entonces
S ⇒ aSb
⇒ aaSbb
..
.
⇒ an Sbn
⇒ an bn = w
i.e., w = an bn para algún n. Por lo tanto
L(G) = {an bn | n ≥ 0}
es un lenguaje independiente del contexto que no es regular, como puede notarse
de la siguiente propiedad.
Propiedad 7. El lenguaje L = {am bm | m ≥ 0} no es regular.
Proof. Supongamos que L es regular. Sea n la cosntante del lema del bombeo
para L y consideremos la palabra w = an bn que evidentemente pertenece a L.
Tenemos que |w| = 2n ≥ n. Entonces podemos escribir
w = uvx
con |uv| ≤ n, |v| ≥ 1 y ∀i ≥ 0, uv i x ∈ L.
Como |uv| ≤ n entonces uv está formado sólo por a’s:
w=a · · a} |· · · ab
| ·{z {z· · · }b
uv x
r s
ası́ u = a , v = a para algunos o ≤ r ≤ n, 1 ≤ s ≤ n. Lo que implica
x = an−r−s bn
luego, bombeamos con i = 2:

L 3 uv 2 x = ar a2 san−r−s bn
= an+s bn
con s ≥ 1. Lo cual es imposible.
Por tanto L no es regular.

El nombre independiente del contexto es para diferenciarlas de las gramáticas que
son sensibles al contexto; en éstas las producciones son de la forma
α1 Aα2 → α1 Bα2
i.e, dependen del contexto.
Tarea 14. (1) Dada la gramática independiente del contexto
S → AA
A → AAA|a|bA|Ab
(a) Obtener una derivación para la cadena b2 aba2 ba

(2) Dada la gramática independiente del contexto
S → AA
A → AAA|a|bA|Ab
(a) Obtener una derivación para la cadena b2 aba2 ba

(b) Probar c´’mo puede obtenerse una derivación para bm1 abm2 a . . . bm2n abm2n+1 ,
para todo n > 0 y m1 , m2 , . . . , m2n+1 ≥ 0.
(3) La gramática G independiente del contexto dada por
S → aSb|aSa|bSa|bSb|
no es una gramática regular, aunque L(G) es un lenguaje regular! Obtener
una gramática regular G0 tal que L(G0 ) = L(G).
(4) Obtener una gramática indeoendiente del contexto para cada uno de los
siguientes lenguajes independientes del contexto:
(a) {am bn | m ≥ n}
(b) {am bn | n ≤ m ≤ 2n}
4. Árboles de derivación ó análisis

Una forma de visualizar las derivaciones de la gramáticas independientes del con-
texto es con los árboles de derivación ó árboles de análisis. Este cosniste de un
nodo raı́z que es el sı́mbolo inicial. Luego el nodo raı́z tiene nodos hijos, uno por cada
sı́mbolo que aparezca en el cuerpo de la producción usada para reeemplazar el sı́mbolo
inicial. Cada nodo no terminal tendrá hijos a su vez dados por la producción usada al
substituir. Por ejemplo, consideremos la gramática G:
(1) S → AB
(2) A → aA | a
(3) B → bB | b
4. ÁRBOLES DE DERIVACIÓN Ó ANÁLISIS 77
entonces aabbb ∈ L(G) pues puede ser generada por
(1)
S ⇒ AB
(3)
⇒ AbB
(3)
⇒ AbbB
(3)
⇒ Abbb
(2)
aAbbb
(2)
aaabbb
que le corresponde árbol de derivación
Si leemos las hojas de izquierda a derecha obtenemos aabbb.

Nótese que se puede derivar a2 b3 de muchas formas:
(1)
S ⇒ AB
(2)
⇒ aAB
(2)
⇒ aaB
(3)
⇒ aabB
(3)
⇒ aabbB
⇒ aabbb
cuyo árbol de derivación resulta:

que es el mismo que antes. Otra posible derivación de a 2 b3 es
S ⇒ AB
⇒ aAB
⇒ aAbB
⇒ aAbbB
⇒ aAbbb
⇒ aabbb
cuyo árbol de derivación es de nuevo, el mismo que antes. Resulta que todos los árboles
de derivación de a2 b3 tienen el mismo árbol. Este no es siempre el caso. Por ejemplo,
en la gramática,
S → SbS | ScS | a
se puede derivar la cadena abaca de dos formas:

(1)
S ⇒ SbS
⇒ SbScS
⇒ SbSca
⇒ Sbaca
⇒ abaca
(2)
S ⇒ ScS
⇒ SbScS
⇒ abScS
⇒ abacS
⇒ abaca
cuyos árboles de derivación son:

4. ÁRBOLES DE DERIVACIÓN Ó ANÁLISIS 79
(a)
(b)
que son diferentes.
Las cadenas derivadas corresponden a las hojas de los árboles de derivación y se
llaman producto del árbol de derivación .
Definición 41. Una gramática G se llama

(1) ambigua si ∃w ∈ L(G) tal que w tiene al menos dos árboles de derivación
diferentes.
(2) no ambigua si ∀w ∈ L(G), w tiene todos sus árboles de derivación
iguales.
La ambiguedad ocurre en los lenguajes “naturales”. Por ejemplo

Pedro vió a un hombre con un telescopio
significa que ¿ Pedro usó un telescopio para ver a un hombre? ó que ¿ Pedro vió a un
hombre que tenı́a un telescopio?.
También las ambiguedades aparecen en las expresiones algebraicas:
Ejemplo 68. Consideremos la gramática
A → I := E
I → a |b | c
E → E + E |E ∗ E | (E) | I
(las mayúsculas son no terminales; los demás sı́mbolos, ”:=”, ”*”, ”(”,”(” son
terminales). La cadena
a := b + c ∗ a
se puede derivar de formas diferentes:

ó
En algunos casos , se puede encontrar una gramática que produzca el mismo

lenguaje, pero que no sea ambigua. Si esto no es posible, entonces el elnguaje se
llama inherentemente ambiguo.
Tarea 15. Demostrar que la gramática es ambigua

S → bA|aB
A → a|aS|bAA
B → b|bS|aBB
5. Simplificación de las GIC

Las gramáticas pueden tener árboles de derivación innecesariamente complicados:
5. SIMPLIFICACIÓN DE LAS GIC 81
(1) S → abcdef gS | abcdef g que le corresponde árboles de derivación como los

siguientes
(2)
S→A
A→B
B→C
C →D
D → a|A
Lo importante de una grmt́ica es el lenguaje que genera. Se pretende tener

gramáticas razonables que generen los mismos lenguajes: lo primero que se hace es
eliminar las producciones y sı́mbolos inútiles.
Definición 42. Sea G = (N, |sigma, S, P ) una GIC y X ∈ N ∪ Σ. Se dice que
(1) X es útil si existe una derivación de la forma
∗ ∗
S ⇒ αXβ ⇒ w
con w ∈ Σ∗ .
(2) X es inútil si no es útil.
∗
(3) X es generador si X ⇒ w para algún w ∈ Σ∗ .
(4) X es alcanzable si existe una derivación de la forma
∗
S ⇒ αXβ.
Ejemplo 69.
G: S → Aa | B | D
B→b
A → aA | bA | B
C → abd
Obérvese que C nunca forma parte de una derivación de una palabra generada:
S ⇒ · · · ⇒ αCβ ⇒ · · · ⇒ w ∈ Σ∗
es imposible. Ası́ C y la producción C → aba son inútiles.

Tampoco D es generador y por tanto nunca deriva (ó forma parte de una
dericación productiva). En este sentido D es un sı́mbolo inútil.
El siguiente algoritmo elimina los sı́mbolos no terminales que no son generadores.

entrada: G = (N, Σ, S, P ) una GIC
salida: G0 = (N 0 , Σ, S, P 0 ) una GIC tal que L(G0 ) = L(G) y
∗
∀A ∈ N 0 , A⇒w
con w ∈ Σ∗ (no necesariamente A = S).

Algoritmo 3.5.1: (1) Inicializar N 0 con los no terminales A para los cuales A → w es una
producción de G, con w ∈ Σ∗ .
(2) Inicializar P 0 con todas las producciones A → w con A ∈ N 0 y w ∈ Σ0 .
(3) Repetir:
(
Añadir a N 0 todos los no terminales A para los cuales
A → w es una producción de G con w ∈ Σ∗ .
hasta que no se puedan añadir más terminales a N 0 .
Ejemplo 70. Le aplicaremos el algoritmo descrito a
G: S → Aa | B | D
B→b
A → aA | bA |B
C → abd
Comenzamos con N 0 = {B, C} y
P0 : B→b
C → abd
1er pasada del ciclo:
N 0 = {B, C} ∪ {A} P0 : B→b

C → abd
A→B
2da pasada del ciclo:

N 0 = {B, C, A} ∪ {S} P0 : B→b
C → abd
A→B
S → Aa | B
A → aA | bA
3er pasada del ciclo: fin. queda
G :S → Aa | B
A → aA | bA | B
B→b
C → abd
Se permiten producciones del tipo A → . Por ejemplo.
G :S → aA |
A → aA | bB |
B → bB
Las inicializaciones del algoritmo anterior quedan:
N 0 = {S, A}, P0 : S→
A→
1er pasada del ciclo:
N 0 = {S, A} P0 : S → | aA
A → aA | bB |
B→b
2da pasada del ciclo:
N 0 = {S, A} P0 : S→
A→
S → aA
A → aA
3er pasada: fin.
Salida:
G0 : S → aA |
A → aA |
En el ejemplo 70, el algoritmo 3.5.1 no eliminó la última producción C → abc
que no es productiva pues C no es alcanzable. El siguiente algoritmo elimina los
inalcanzables
entrada: G = (N, Σ, S, P ) una GIC.
salida: G0 = (N 0 , Σ0 , S, P 0 ) una GIC tal que L(G0 ) = L(G) y todos los sı́mbolos de
N 0 son alcanzables.
Algoritmo 3.5.2: (1) Inicializar N 0 = {S}, P 0 = , Σ0 =
(2) Para cada A ∈ N 0 , para cada A → w en P hacer:

(a) Introducir A → w en P 0 .
(b) Para todo B no terminal que forma w introducir B en N 0 .
(c) Para todo terminal σ que forma w introducir σ en Σ0 .
hasta que no se puedan añadir nuevas producciones.
Ejemplo 71.
G: S → Aa | B
B→b
A → aA | bA | B
C → abd
y le aplicamos el algoritmo 3.5.2:
inicialización: N 0 = {S}, P 0 = , Σ0 = .
primer pasada: tenemos S ∈ N 0 (A = S en el algoritmo) y
S → Aa
S→B
en P;
(1) P 0 : S → Aa | B
(2) N 0 = {S, A, B}
(3) Σ0 = {a}
2da pasada: S ∈ N 0 ya;
A ∈ N 0 : (1)
P0 : S → Aa | B
A → aA | bA
(2) N 0 = {S, A, B}
(3) Σ0 = {a} ∪ {b} = {a, b}
0
B ∈ N : (1)
P0 : S → Aa | B
A → aB | bA
B→b
(2) N 0 = {S, A, B}
(3) Σ0 = {a, b}
3er pasaa: no se pueden añadir más producciones: fin.
Salida:
G0 : S → Aa | B
A → aA | bA
B→b
con alfabeto Σ = {a, b}.
Nótese que se han eliminado C y d.
Finalmente, para quitar los sı́mbolos inútiles e improductivos se aplican los algo-
ritmos 3.5.1 y a la gramática de ésta salida se le aplica el algoritmo 3.5.2 y en este
orden. Los algoritmos 3.5.1 y 3.5.2 no conmutan, i.e., el orden de su aplicación cambia
las salidas. Por ejemplo, para la gramática
G: S → AB | a
A→a
puede notarse que B no es necesario. Le aplicamos a G el algoritmo 3.5.1 y a la

gramática que resulte le aplicamos el 3.5.2 parta quitar los improductivos.
(
3.5.1 S → a 3.5.2 n
G −→ −→ S → a
A→a
siendo ésta última la gramática esperada. Pero si aplicamos los algoritmos en el otro
orden
( (
3.5.2 S → AB | a 3.5.1 S → a
G −→ −→
A→a A→a
que no es la respuesta esperada.
Tarea 16. (1) Aplicar el algoritmo 3.5.1 a las siguientes gramáticas:

(a)
S → aAb|cEB|CE
A → dBE|eeC
B → f f |D
C → gF B|ae
D→h
(b)
S → aB
A → bcCCC|dA
B→e
C → fA
D → Dgh
(c)
S → a|aA|B|C
A → aB|
B → Aa
C → bCD
D → ccc
(2) Aplicar el algoritmo 3.5.2 a las siguientes gramáticas independiente del

contexto
(a)
S → aAb
A → ccC
B → dd|D
C → ae
D→f
U → gW
W →h
(b)
S → a|aA|B
A → aB|
B → Aa
D → ddd
(3) Eliminar los sı́mbolos inútiles de la siguiente gramática por medio de los
algoritmos 3.5.1 y 3.5.2:
S → A|AA|AAA
A → ABa|ACa|a
B → ABa|Ab|a
C → Cab|CC
D → CD|Cd|CEa
E→b
6. Eliminación de las producciones

Definición 43. Una producción del tipo A → se llama producción .
Sea G una GIC. Si 6∈ L(G) entonces se peuden eliminar todas las producciones
. Si ∈ L(G) también se pueden eliminar todas la producciones exepto una.
Definición 44. Si A es no terminal, A se dice anulable si
∗
A⇒
El siguiente algoritmo calcula η el conjunto de todos los anulables y está basado
∗
en que si A → X1 · · · Xn y cada Xi ⇒ entonces A es anulable.
salida: η el conjunto de todos los anulables.
procedimiento: (1) Inicio: η = {A ∈ N | A → }
(2) Repetir hasta que no se puedan añadir más terminales a η: Si B → w
en P y w ∈ η ∗ , añadir B a η.
Para obtener una G0 GIC sin producciones se crea un conjunto de producciones
0
P como: si B → X1 · · · Xn en P esta se cambia por proucciones B : Y1 · · · Yn donde
(
X1 si Xi no es anulable
Yi =
Yi = X1 ó Yi = si Xi es anulable
6. ELIMINACIÓN DE LAS PRODUCCIONES 87
pero no (∀i, Yi = ). Es decir, se añaden producciones donde los anulables X i aparecen
ó no, pero sin incluir a las producciones .
Ejemplo 72. Sea
G: S → aA
A → aA |
Queremos encontrar G0 una GIC tal que L(G0 ) = L(G) pero G0 sin producciones .
Primero calculamos el conjunto de anulables:
inicio: η = {A}
ciclo: fin
Cambiamos ahora las producciones (donde A esté presente ó ausente)
G0 S → a | aA
A → a | aA
Comoe 6∈ L(G), entonces L(G0 ) = L(G).
Ejemplo 73.
G: S → AB
A → aAA |
B → bBB |
Encontraremos una gramática G0 sin producciones tal que L(G0 ) = L(G) − {}
(nótese que ∈ L(G)).
Primero calculamos los anulables:
Inicio: η = {A, B}
ciclo: como S → AB con AB ∈ η ∗ entonces S ∈ η. Fin.
Resulta η = {A, B, S} (todos los sı́mbolos no terminales son anulables). Ahora
reeemplazamos las producciones de G por ausencia o no de los anulables:
de S → AB se obtienen
S → A | B | AB
de A → aAA se obtienen
A → aAA | aA | a
y de B → bBB se obtienen
B → bBB | bB | b
Resulta entonces
G0 : S → A | B | AB
A → aAA | aA | a
B → bBB | bB |b
tal que L(G0 ) = L(G) − {}.
Tarea 17. (1) Obtener la colección de no terminales anulables que pertenecen
a la siguiente gramática:
S → aA|bA|a
A → aA|bAb|
(2) Obtener, para la siguiente gramática, el número de no terminales anula-

bles:
S → ABaC
A → AB
B → b|
C → D|
D→d
(3) Eliminar las producciones de las gramáticas:

(a)
S → aA|bA|a
A → aA|bAb|
(b)
S → AB
A → aA|abB|aCa
B → bA|BB|
C→
D → dB|BCB
(c)
S → a|aA|B
A → aB|
B → Aa
(4) El lenguaje asociado con la siguiente GIC contiene . Eliminar las pro-
ducciones exepto S → .
S → AB|aB|
A → BBB|aB|a|
B → a|aA|
(5) Eliminar todas las producciones unitarias de las siguientes GIC:

(a)
S → CBa|D
A → bbC
B → Sc|ddd
C → eA|f |C
D → E|SABC
E → gh
7. ELIMINACIÓN DE PRODUCCIONES UNITARIAS 89
(b)
S → Aa|Ba|B
A → Aa|
B → aA|BB|
Obsérvese que ∈ L(G).
7. Eliminación de producciones unitarias

Definición 45. Una producción unitaria es una del tipo A → B con A, B
no terminales.
A veces son útiles las producciones unitarias, pero otras veces son indesables pues
complican los árboles de derivación. Nos proponemos eliminar tales producciones uni-
tarias.
Definición 46.
(1) A ⇒ A usando cero producciones.
(2) Si A es no terminal
∗
U (A) = {B ∈ N | A ⇒ B usando solamente producciones unitarias ó cero producciones}
Nótese que ∀A,
A ∈ U (A).
El siguiente algoritmo elimina las producciones unitarias:

salida: G0 = (N, Σ, S, P 0 ) una GIC sin producciones unitarias tal que L(G0 ) = L(G)
procedimiento: (1) Inicializar P 0 =
(2) ∀A ∈ N , obtener U (A)
(3) Para cada A ∈ N , para cada B ∈ U (A), para cada producción no
unitaria B → w de P añadir A → w en P 0 .
Tarea 18.
(1) Convertir las siguientes GIC a forma normal de Chomsky:
(a)
S → AB|CA
A→a
B → BC|AB
C → aB|b
(b)
S → aAb|cHB|CH
A → dBH|eeC
B → f f |D
C → gF B|ah
D→i
E → jF
F → dcGGG|cF
G → kF
H → Hlm
Tarea 19. (1) Probar que cada uno de los siguientes lenguajes no son
lenguajes independientes del contexto.
(a) {ai bi ci | i ≥ 1}
(b) {ai bi cj | j ≥ i}
(c) {ai bj cj | i ≤ j ≤ k}
(d) {ai | i es primo}
(e) {w ∈ {a, b, c}∗ | n ≤ m ≤ 2n}
(f) {ww | w ∈ {a, b}∗ }
(2) Obtener un autómata a pila que acepte {an bn | n ≥ 0}.
(3) Describir los cambios de configuraciones sobre las cadenas abaababb y abaa
realizados por el autómata a pila siguiente (con sı́mbolo inicial de pila Z):
a, B/
b, A/
a, Z/AZ R
- r , Z/Z- rj
b, Z/BZ q1
q2
a, A/AA
b, B/BB
¿son aceptadas?.
(4) Los mismo que el anterior para las cadenas c, abcba, abcab y babbcbbab y
el autómata a pila
7. ELIMINACIÓN DE PRODUCCIONES UNITARIAS 91
b, b/
a, a/
, Z/Z R
- r - r - rg
q1 I
@ q2 q3
@
, Z/Z
a, Z/aZ
a, a/aa
a, b/ab
b, Z/bZ
b, a/ba
b, b/bb
c, Z/Z
c, a/a
c, b/b
CHAPTER 3
Máquinas de Turing
1. Definición y termininologı́a
Definición 47. Una máquina de Turing es una 7-tupla:
M = (Q, Σ, Γ, s, B, F, δ)
donde
• Q es un conjunto finito de estados.
• Σ es un alfabeto de entrada.
• Γ es un alfabeto llamado de entrada.
• s ∈ Q estado inicial.
• Γ es alfabeto llamado de cinta, con Γ ⊇ Σ.
• B ∈ Γ pero B 6∈ Σ llamado sı́mbolo blanco.
• F ⊆ Q estados finales. δ : Q × Γ → Q × Γ × {L, R} es una función parcial
llamada función de transición
Aclaramos que, en general, una función parcial g : A → B es una re lación de A

en B tal que ∀a ∈ A, g(a) es a lo más un elemento.
Ejemplo 74. Sea f : → , f (x) = 1/x es función parcial. Nótese que f (0)
no está definida.
Ejemplo 75. Sea g : (−1, 1), g(x) = log(x) también es una función parcial
pues g no está definida en (−1, 0].
Si M es una MT con funciónde transición δ, entonces

δ(q, γ) = (p, τ, X)
donde
(1) q es estado actual, γ es sı́mbolo de cinta leı́do
(2) p es estado siguiente, τ es sı́mbolo escrito en cinta.
(3) X es un movimiento de escritura/lectura de cabeza que puede ser L
(izquierda) ó R (derecha).
Toda ésta teminologı́a se debe a que las MT se interpretan como mecanismos que
constan de una cinta infinita hacia la izquierda y hacia la derecha, separada en celdas
que contienen a los sı́mbolos de cinta:
··· B B B a b b c B B ···
Tal cinta está casi llena de sı́mbolos blancos. Sólo una porción finita entre sı́mbolos
blancos contiene la información que interesa.
93
94 3. MÁQUINAS DE TURING
Las MT cambian sus configuraciones celda por celda, senalando la celda a modificar
con una cabeza de cinta. Por ejemplo;
δ(q1 , a) = (q5 , b, R)
indica que si
a b b
6 estado q0
entonces
b b b
6
estado q1
Ejemplo 76. Sea M la MT definida por

• Q = {q0 , q1 }
• Σ = {a, b}
• Γ = {a, b, B}
• F = {q1 }
• s = q0
y transiciones dadas por
δ a b B
q0 (q0 , a, R) (q0 , a, R) (q1 , R, L)
q1
Inciamos con configuración
a b b a
6 estado q0
y entonces tenemos los siguientes cambios de configuración
a b b a a b b a a a b a
6 estado q0 6 estado q0 6
estado q0
a a a a B a a a a B
6 estado q0 6 estado q0
a a a a B
6 estado q1
1. DEFINICIÓN Y TERMININOLOGÍA 95
Nótese que se ha insertado B que se sobreentiende siempre aparece a la izquierda y a

la derecha de la palabra escrita en cinta.
Tales cambios de confuguración se pueden denotar más brevemente si se usa la
notación torniquete; hay al menos dos variantes
(1)
(q0 , abba) ` (q0 , abba)
` (q0 , aaba)
` (q0 , aaaa)
` (q0 , aaaaB)
` (q1 , aaaa)
(2)
q0 abba ` aq1 bba
` aaq1 ba
` aaaq1 a
` aaaaq1 B
` aaaq2 a
Las MT tambı́en tienen diagramas de transición similares a los autómatas de pila.
Por ejemplo, el diagrama de transición de la MT del ejemplo inmediato anterior es
Ejemplo 77. Sea M la máquina de Turing definida por el diagrama
entonces
aabq1 abb ` aaq1 babb
` aq1 ababb
` q1 aababb
` q1 Baababb
` Bq2 aababb = q2 aababb
` q3 Baababb
y entonces la máquina se detiene.
Ejemplo 78. Consideremos la máquina de Turing
96 3. MÁQUINAS DE TURING
aquı́ el conjunto de estado finales es F = y el alfabeto de entrada es Σ = {a, b.

Para cualquier w ∈ Σ∗ tenemos que
q1 abw ` aq2 w
` q1 aw
` aq2 bw
` q1 abw
` ...
y la MT nunca para (bucle infinito). Se pone
q1 abwstackrel∗`∞
para indicar que comenzando en la configuración qa bw la máquina nunca para.
2. Aceptación
Definición 48. Sea M = (Q, Σ, Γ, s, B, F, δ) una MT. El lenguaje aceptado
por M es
L(M ) = {w ∈ Σ∗ | sw ` w1 pw2 , con w1 , w2 ∈ Γ∗ , p ∈ F }
Tarea 20.
(1) Construir una máquina de Turing que analice una cadena de {a, b} + de-
splazándose por la cinta de izuqierda a derecha y que reeemplace cada b’s
por c. La máquina de Turing deberı́a comenzar con la cabeza sobrte el
primer sı́mbolo (el que está más a la izquierda) de la cadena y terminar
su cabeza sobre el blanco final (el blanco que sigue a la a o a la c que esté
más a la derecha en la cadena transformada).
(2) Construir una máquina de Turing que enumere todos los enteros binarios,
en orden numérico sobre su cinta cuando comience con (q1 , 0B). Es decir,
la máquina de Turing debe ejecutarse de esta forma:
∗ ∗ ∗ ∗
(q1 , 0B) ` (q1 , 1B) ` (q1 , 10B) ` (q1 , 11B) ` · · ·

Tutorial Lenguajes Formales y Automatas

Cargado por

Copyright:

Formatos disponibles

Tutorial Lenguajes Formales y Automatas

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Tutorial Lenguajes Formales y Automatas

Cargado por

Copyright:

Formatos disponibles

Contents

Chapter 1. Autómata finito 5

César Bautista Ramos

Estudiaremos lenguajes formales, esto es “matemáticos”; no confundirlos con los

No debemos confundir a la palabra vacı́a  con el lenguaje vacı́o:

Definición 8 (potencia). Si n ∈ y w ∈ Σ∗ , se define

llamada la n-ésima potencia de w.

Ejemplo 10. Si w = 122 entonces

La igualdad entre palabras se podrı́a definir como: si w, z ∈ Σ ∗ , se pone w = z en

(2) Se dice que x es prefijo propio de w si x es prefijo de w, pero w 6= x.

Ejemplo 11. Sea w = 121. Entonces

Definición 10. Una cadena w ∈ Σ∗ es subpalabra de z ∈ Σ∗ si ∃x, y ∈ Σ∗

(2) w = 2 es subpalabra de z = 121; a su vez y = 12 es subpalabra de z, pues

El siguiente concepto será útil para definir nuevos lenguajes.

Definición 11. Si w ∈ Σ∗ , la inversa o transpuesta de w es la imagen

Ejemplo 13. Si w = ecos, entonces

3. Operaciones con lenguajes

(2) La cerradura positiva de A es

La cerradura de Kleene se obtiene al hacer cero o más concateneaciones de las

Propiedad 3. Si A es un lenguaje sobre Σ, entonces

Ejemplo 20. Tenemos que es un lenguaje. Entonces

Por demostrar que (A+ )k+1 ⊆ A+ . Tenemos que

Por lo tanto (A · B)I ⊆ B I · AI .

Podemos enumerar las palabras según este orden

En contraste todos los lenguajes que se pueden formar con Σ no es numerable. Es

Teorema 4. Sea Σ un alfabeto. El conjunto de los lenguajes sobre Σ no es

Procedemos por contradicción. Supongamos que L es numerable. Entonces

Sabemos que Σ∗ es numerable, entonces podemos poner

definimos entonces el conjunto diagonal,

D es un lenguaje sobre Σ∗ , entonces D ∈ L, por lo que debe de existir k ∈ tal

Tenemos dos casos wk ∈ D o wk 6∈ D.

5. Lenguajes Regulares y Expresiones Regulares

son lenguajes regulares.

Ejemplo 24. Sea Σ = {a, b}. Entonces

{ai bj | i ≥ 0 y j ≥ 0} = {a}∗ · {b}∗ es regular

{(ab) | i ≥ 0} = {ab}∗ es regular .

Ejemplo 25. Sea Σ = {a, b, c} y A el lenguaje sobre Σ:

(3) Si r y s son expresiones regulares entonces

Definición 22. Sean r, s expresiones regulares sobre Σ. Se dice que r y s son

(7) r(st) = (rs)t

(4) Para una palabra w, ¿se puede decir que

(h) ( ∪ aa)( ∪ aa)∗ (ab ∪ b) ∪ (ab ∪ b).

6. Autómatas finitos deterministas

Figure 1. Un autómata finito determinista

Tales grafos se llaman autómatas finitos deterministas (AFD).

se arriba entonces a un estado que no es de aceptación, por lo que la palabra aba

Ejemplo 31. Lo mismo que el anterior para A = (ab)∗ .

Por lo que el autómata pedido es

Nótese que ahora tenemos dos estados finales.

se acepta sólo a al lenguaje a(ba)∗ y no a la palabra vacı́a. Si ponemos al estado inicial

Entonces se puede representar la dinámica de los estados mediante una tabla

que es una forma de representar a una función δ : Q × Σ → Q, donde Q =

Ejemplo 35. Sea M = (Q, Σ, s, F, δ) con Q = {q0 , q1 , q2 , q3 }, Σ = {a, b},

Definición 24. Sea M un AFD. El lenguaje aceptado por M es

Definición 26. Sean M1 , M2 dos AFD. Se dice que M1 es equivalente a M2

Ejemplo 37. Pongamos Σ = {a} Sea M1 el autómata finito determinista dado

Tarea 6. (1) Obtener la expresión regular que representa el lenguaje for-

y δ dada por la tabla

No debemos confundir a la palabra vacı́a con el lenguaje vacı́o:

(h) ( ∪ aa)( ∪ aa)∗ (ab ∪ b) ∪ (ab ∪ b).

M es un AFN con -transiciones. Nótese que se puede transitar del estado q2 a q0

Definición 33. Sea q un estado. La -cerradura de q es

primero calculamos su -cerradura:

podemos encontrar M 0 un AFN sin -transiciones equivalente a M : por con-

los estados finales de M 0 son F 0 = {q | ( − c)(q) ∩ F 6= }:

∆0 (q, σ) = ( − c)(d(( − c)(q), σ))

- q0r - qr1 - qr2f

- q0r - qr1 - qr2f

dependiente de la -transición hacia q3 ó q4 , donde A y B son también sı́mbolos no