Automatas y Lenguajes

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES NICOLÁS KOVAC NEUMANN (Revisado Julio/2005)
TEORÍA
DE
AUTÓMATAS
Y LENGUAJES
FORMALES
2
A
T 1
L 4
F
3
1
Breve comentario introductorio
Estos apuntes no quieren (ni mucho menos) sustituir los que impartirá el profesor de la
asignatura. Sirven únicamente como una especie de "bastón" a la hora de estudiar la
asignatura. Fueron tomados en el Curso 2003/2004 y los he intentado organizar de
alguna forma para poder pasarlos a ordenador y posteriormente ponerlo a disposición de
la gente. Es muy posible que encuentren más de una errata, estos apuntes fueron
tomados por mí en clase, por lo que me he podido equivocar hasta copiando de la
pizarra. De ser así ruego me lo comuniquen para corregirlo lo antes posible.
He obviado pasar el tema 0 del curso, que es una introducción al C++, porque en mi
opinión no tienen nada que ver con el contenido real de la asignatura, y quiero
centrarme estrictamente en el contenido de la materia.
Los títulos en rojo anuncian el comienzo de un nuevo tema, que explicaré hasta
que aparezca otro título en rojo o se termine el temario.
Los títulos en azul corresponden a subapartados de un determinado tema, que

también explico a continuación.
Def: corresponde a una definición de algún término o términos, que aparecen

subrayados.
Teor: corresponde al enunciado de algún teorema.
Dem: implica el inicio de una demostración.
Agradecimientos a: David Taima Hernández por la notable mejora de los dibujos.
Espero que estos apuntes les sirvan de algo... un saludo.
Cualquier cosa que me quieran comunicar, sean erratas, comentarios, etc., lo pueden
hacer a la siguiente dirección de correo: [email protected]
2
TEMARIO DE LA ASIGNATURA
Tema 1: Conceptos Previos
Tema 2: Conceptos Básicos
Tema 3: Lenguajes regulares y Autómatas Finitos
Tema 4: Gramáticas. Lenguajes Independientes del Contexto
Tema 5: Máquinas de Turing
Tema 6: Resolubilidad
3
Tema 1
Conceptos Previos.
Lógica Proposicional.
• Equivalencia P ≡ Q Significa que P es equivalente a Q, siempre que P es cierto
⇒ Q es cierto, y siempre que P es falso ⇒ Q es falso.
P. ej: "3 es entero" ≡ "Ν es finito" (ambas falsas)

5
• Negación (p → ¬p)
Tabla de verdad
p ¬p
F T
T F
(F = False, T = True)
• Conjunción (p ∧ q)
Tabla de verdad
p q p∧q
F F F
F T F
T F F
T T T
• Disyunción (p ∨ q)
Tabla de verdad
p q p∨q
F F F
F T T
T F T
T T T
• Condicional (p → q)
Cuando hablamos de una proposición condicional, de la forma p → q, a "p" se

le llama hipótesis o antecedente, y a "q" se le llama consecuente o conclusión.
Tabla de verdad
p q p→q
F F T
F T T
T F F
T T T
4
• Recíproca (q → p)
La tabla de verdad se saca fácilmente viendo el ejemplo anterior
• Contrapuesta (¬q → ¬p)

Tabla de verdad
p q ¬q → ¬p
F F T
F T T
T F F
T T T
Como se puede apreciar, la Contrapuesta es equivalente a la Condicional.

bicondicional
Si (p → q) ∧ (q → p) = p ↔ q
Es equivalente a decir, p sii (si y sólo si) q.
Si p y q son equivalentes, entonces p ↔ q es una tautología.
Def: Una tautología es una proposición siempre cierta.

Def: Una contradicción es una proposición siempre falsa.
Si p → q es una tautología, se escribe p ⇒ q

Si p ↔ q es una tautología, se escribe p ⇔ q
Def: Se llama p(x) a una frase abierta o función proposicional, donde

"x" es la variable proposicional.
P. ej.: x² - 1 = 0. Esta ecuación depende de la variable "x".
Def: Se llama "Conjunto de significados de una variable" al conjunto de

entidades que pueden sustituir a las variables.
P. ej.: Sea A = {1, 2, 3}.

¿Existe algún elemento de A que haga cierta la ecuación
del ejemplo anterior? Vemos que el 1 la hace cierta, luego
A es un conjunto.
5
Def: Se llama "Conjunto de verdad" a aquel subconjunto del conjunto

de significados que hace cierta la función.
P. ej:
La función Conjunto de significados Conjunto de verdades

{1, 2, 3} {1}
x² - 1 = 0 {Ν} {1}
{Ρ} { 1, -1 }
• Cuantificadores
Son cuantificadores los siguientes símbolos:
Universal
Para todo x, P(x) es verdadera
∀ x, P(x)
Existencial
Existe un x del conjunto de significados para el que P(x) es cierta
· ·
∃ x P(x), ∃ x P(x) ( ∃ = "Existe un único")
Sea | (tal que)
Teor: ¬ ( ∀ x P(x)) ≡ ∃ x | ¬P(x).
__________________________________________________________
Teoría de conjuntos.
Se denotarán los conjuntos con letras mayúsculas, y los elementos con letras
minúsculas.
Sea el conjunto de las vocales, A = {a, e, i, o, u}.

Sea el conjunto de los números naturales, Ν = {0, 1, 2, 3, ...}.
Sea el conjunto de las letras, L = {a, b, c, d, e, f ...}.
a ∈ A (a pertenece al conjunto de las vocales).

b ∉ A (b no pertenece al conjunto de las vocales) .
a, b ∉ Ν (a, b no pertenecen al conjunto de los números).

a, b ∈ L (a, b pertenecen al conjunto de las letras).
6
Teor: Dos conjuntos son iguales si contienen los mismos elementos.
Def: Se denomina cardinal de un conjunto, y se representa por |A|,

siendo A el nombre del conjunto, al número de elementos de dicho
conjunto.
Algunas cuestiones de notación:
a ≠ {a} ; el ELEMENTO "a" es distinto al CONJUNTO que contiene "a".

a ∈ {a} ; el elemento a es subconjunto del conjunto que lo contiene.
A ⊆ B ; se dice que A está contenido en B.
{a, b} ≠ {{a, b}} ; el conjunto {a, b} es distinto del conjunto que lo contiene.
Teor: (A ⊆ B) ∧ (B ⊆ A) ⇔ A = B.
Teor: Si (A ⊆ B) ∧ (B ⊆ C) ⇒ A ⊆ B.
Def: Existe el llamado Conjunto Vacío ( ∅ ), que es el que no tiene

ningún elemento. ∅ ⊆ A, ∀ A (el vacío es subconjunto de todo
conjunto).
Def: Se denomina Conjunto Potencia al conjunto de todos los

subconjuntos de A.
Se denota por ℘ (A). Este conjunto debe tener 2 A elementos.
P. ej.: A = {0, 1}
2 A =℘ (A) = {{0}, {1}, {0, 1}, { ∅ }}
{ ∅ } ∈ 2A , ∀ A
| 2 A | = 2 |A|
A ∈, 2 A ∀ A
Def: Definición de Familia Indexada de Conjuntos.

Sea I conjunto.
Si ∀ α ∈I, A α es un conjunto, {A α | α ∈I} se llama F.I.C.
P.ej.:
1 1
Si ∀ n > 0, An = [- , ], { An | n∈Ν, n > 0 } es F.I.C.
n n
1 1
An = { [-1, 1], [- , ], .... }
2 2
7
Operaciones con conjuntos.
• Unión (A ∪ B) = {x | x∈A ∨ x∈B}

• Intersección (A ∩ B) = {x | x∈A ∧ x∈B}
• Complemento de B relativo a A (A - B) = {x | x∈A ∧ x∉B}
Def: A y B son disjuntos si no tienen elementos comunes, es decir, si

A∩ B = {∅}
Def: Se llama U al conjunto universal
Ejemplos:
U - A = {x | x∈U ∧ x∉A}, también se denomina conjunto
−
complementario de A, se denota también: A
−
U=∅
−
∅= U
Teor:
_______ __ __
1) A ∪ B = A ∩ B
_______ __ __
2) A ∩ B = A ∪ B
=
3) A = A (doble complementación)
__
4) A - B = A ∩ B
Def: Se define el Producto Cartesiano como:

A× B = {(a, b) | a∈A ∧ b∈B}
(a, b) = (a', b') ⇔ a = a' ∧ b = b'
Def: Se define una relación como:

A ℜ B, si (a, b)∈ ℜ ⇒ a ℜ b
Ejemplos:
ℜ ⊆ A× A (relación sobre A)
ℜ ⊆ Ν×Ν
(x, y)∈ ℜ si x ≤ y
Def: Se define el Dominio = Dom(R) = {x∈A| ∃ y∈B, (x, y)∈R}
Def: Se define la Imagen = Im(R) = {y∈B| ∃ x∈A, (x, y)∈R}
Def: Se define la partición de un conjunto como:

Sea A ≠ ∅ ,
El conjunto Ψ de subconjuntos de A es una partición de A si
8
verifica:
1) ∀ A, B∈ Ψ , A ∩ B= ∅ , ó bien A=B
B=A
2)
Υ
B∈Ø
P.ej.:
Sea A={0,1,2,3,4,5,6,7,8,9,10}
Ψ = {{0,2,4,6},{1,3,5,7},{8,10},{9}}
La unión de todos los subconjuntos de Ψ da como resultado "A",

con lo cual se cumple la regla 2) antes especificada.
Def: Se define Relación de Equivalencia del siguiente modo:

Sea Ψ una partición de un conjunto X ≠ ∅ .
P.ej.:
Relación sobre X: ℜ ⊆ X× X
ℜ ={(x, y) | x e y están en el mismo conjunto de Ψ }
X={1,2,3}
Ψ ={{1},{2,3}}
ℜ ={(2,3),(2,2),(3,3),(1,1),(3,2)}
Esta relación tiene 3 propiedades:

1) Reflexiva → ∀ a∈X, (a, a)∈ ℜ
2) Simétrica → ∀ x, y∈X, x ℜ y ⇒ y ℜ x
3) Transitiva → ∀ x, y, z∈X, x ℜ y ∧ y ℜ z ⇒ x ℜ z
Si cumple las tres propiedades, estamos hablando de una relación

de equivalencia.
Def: Se define Clase de equivalencia, como:

Sea ℜ relación de equivalencia sobre X
Sea a∈X,
[a] = clase de equivalencia de a = { y∈X | (a, y)∈ ℜ }
Teor: Las clases de equivalencia de una relación de equivalencia

forman una partición del conjunto sobre el que está definida la
relación.
Teor: Cualquier partición de un conjunto describe una relación de

equivalencia sobre el conjunto.
Def: Se define Función Total de la siguiente manera:

Sea f ⊆ A× B
1) Dom(f) = A
( x, y ) ∈ f 
2)  ⇒y=z
( x, z ) ∈ f 
9
Dicho de otro modo, todos los elementos de A tienen que tener

imagen en B.
Def: Se define Función Parcial de la siguiente manera:

Sea f ⊆ A× B
1) Dom(f) ⊆ A
( x, y ) ∈ f 
2)  ⇒y=z
( x, z ) ∈ f 
En este caso, sin embargo, no todos los elementos deben tener
imagen en B.
Def: Se define Función Inversa como:

Sea y ⊆ B, f −1 (y)={x∈A | f(x) = y, para algún y∈Y}
Def: Se define Función Inyectiva como:

Sea f: A  → B
f es inyectiva si,
( x, y ) ∈ f 
⇒x=z
( z, y) ∈ f 
f(x) = f(z) ⇒ x = z
Def: Se define Función Sobreyectiva como:

Sea f: A  → B
f es sobreyectiva si, ∀ y∈B, ∃ x∈A | f(x) = y
Def: Una Función es Biyectiva si y sólo si es inyectiva y sobre.
Ejemplos:
f: Ν → Ν Función inyectiva y sobreyectiva

x α f(x) = x
g: Ν 
→ Ν
p α g(p) = p+1 Es inyectiva, pero no sobre ( ∃ f −1 (0))
h: Ρ 
→ Ρ Hay elementos de y que no son imágenes
q α h(q) = q² de x, luego no es inyectiva (por ej, los nºs
negativos), y tampoco es sobre porque por
ejemplo el -1 y el 1 tienen la misma imagen.
Def: Se define la Composición de funciones como:

Sean ℜ ⊆ A× B, ℑ ⊆ B× C
ℑ ο ℜ ={(a, c) | ∃ b∈B | (a, b)∈ ℜ ∧ (b, c)∈ ℑ }
Ejemplo:
ℜ = {(0,1),(1,3),(1,2),(0,2)}
10
ℑ = {(1,a),(1,b)}
ℑ ο ℜ ={(0,a), (0,b)}
ℜ οℑ =∅
Sean f, g: A  → A
g οf = {(a, b) | Para algún x∈A, f(a) = x ∧ g(x) = b)}
Ejemplo:
Sean f(x) = x³ - 7 y g(x) = x + 5

f οg(x)=f(g(x)) = f(x + 5) = (x + 5)³ - 7
g οf(x) = g(f(x)) = g(x³ - 7) = x³ - 7 + 5 = x³ - 2
Def: Se define Inducción de la siguiente manera:
Sea A ⊆ Ν,
A es inductivo si:
∀ x∈A, x + 1∈A
Por ejemplo:
{10,11,12,13,14,15...} es inductivo
{1,3,5,7,...} no es inductivo
Si es un conjunto inductivo, y además 0∈Conjunto, Conjunto = Ν.

Dicho de otro modo:
0∈ A 
 es cierta para todo n∈ Ν.
n ⇒ n + 1
Principio de Inducción Matemática.

Dado A ⊆ Ν,
1) 0∈A
2) A es inductivo
Si se cumple 1) y 2), se puede afirmar que A = Ν
Dem:
Sea n + 2 < 3(n + 1)
n n+2 3(n + 1)
0 2 3
1 3 6
2 4 9
3 5 12
Nota: Lo anterior NO es una demostración, lo posterior, sí
11
Sea B = {n∈ Ν | n + 2 < 3(n + 1)}
Es B = Ν? Lo intentaremos demostrar usando la inducción matemática.

?
B= Ν
n+2=2 
1) n = 0;  2 < 3, luego la función es cierta para n=0,
3(n + 1) = 3
luego ya tenemos base de inducción.
2) Sup. n + 2 < 3(n + 1) (Hipótesis de inducción)

?
(n + 1) + 2 < (3((n + 1) + 1) (hay que demostrar si se cumple ∀ n)
(n + 1) + 2 = n + 3 = (n + 2) + 1 < 3(n + 1) + 1 = 3n + 4 < 3n + 6 =

3((n + 1) + 1)
3) Concl.: B = Ν, n + 2 < 3(n + 1), ∀ n∈Ν
Dem P(n): 1 + 3 + 5 + ... + (2n - 1) = n²
n ∑ n²
0 1 1
1 4 4
2 9 9
3 16 16
Como vemos, para n = 0 no vale, sin embargo, sí vale para Ν - {0}
1) Si n = 1, 1 = 1²
2) Sup. 1 + 3 + 5 + ... + (2n - 1) = n²
Hip. de inducción: 1 + 3 + 5 + ... + (2q - 1) = q²
?
1 + 3 + 5 + ... + (2q - 1) + (2(q+1) - 1) = (q + 1)²
1 + 3 + 5 + ... + (w1 - 1) + (2(q + 1) -1) = q² + (2q + 1) = (q + 1)²
3) Luego vemos que P(n) es cierta ∀ n ∈ Ν - {0}
Def: Definición de Cardinalidad:

A y B son equipotentes (A ≅ B) (que tienen el mismo cardinal) si
∃ f: A 
→ B , con f biyectiva.
P. ej.:
{a, b, c} ≅ {1, 2, 3} Como vemos, tienen el mismo cardinal.
12
a 1
b 2
c 3
A≅C 

Teor: B ≅ D  A∪B≅ C∪D
A ∩ B = C ∩ D = ∅ 
Def: Se definen Conjuntos ΝK del siguiente modo:

∀ K∈ Ν, Ν K = {1..K}
A es finito si:
a) A = ∅ , en este caso card|A| = | ∅ | = 0
b) A ≅ B = A K , en este caso card|A|=| Ν K | = K
Υ
B∈Ø
A∩ B = ∅ 
Teor:  |A ∪ B| = |A| + |B|
A, B, finitos 
a) A= ∅ , |A ∪ B|=|B| = 0 + |B| = |A| + |B|

b) B= ∅ , |A ∪ B|=|A| = 0 + |A| = |A| + |B|
c) A ≠ ∅ ∧ B ≠ ∅
|A| = m ⇒ ∃ f: A  → Ν m biyectiva
|B| = n ⇒ ∃ g: B 
→ Ν n biyectiva
Teor: Teorema del palomar
Sea el conjunto P el de las palomas, y N el de los nidos
X
X
*
X
*
X
*
X
X
P N
13
Vemos que hay más palomas que nidos, luego al menos en algún
nido deberá haber más de una paloma, con lo cual:
|P| > |N|

f: P → N, f no es inyectiva.
Corolario (consecuencia menor del teorema):

Si A es finito y B ⊂ A,
B≅ A
Def: Un conjunto es enumerable si A ≅ Ν.

Def: Un conjunto es numerable si es enumerable o finito.
Teor: Sea A enumerable,

Si B ⊆ A, B es infinito
⇓
B es enumerable
Como A es enumerable ⇒ ∃ f: A 
→ Ν ∧ ∃ f: Ν 
→ A
es biyectiva.
f(n) = a n
A={a 0 , a 1 , a 2 .... a n }
Sea h 0 el primer subíndice tal que a n 0 ∈B
Sea h 1 el primer subíndice tal que a n1 ∈B - {a n 0 }
Μ
Sea h k el primer subíndice tal que a nk ∈B - {a n 0 , a n1 , a nk −1 }
⇓
B es enumerable
Teor: Todo conjunto infinito contiene un subconjunto enumerable.

Sea X ≠ ∅ , ∃ x 0 ∈X, ∃ x 1 ∈X, ...
|X| ≤ |Y| si ∃ f: X  → Y inyectiva.
|X| < |Y| si |X| ≤ |Y| ∧ X ≠ Y
Teor: Teorema de Cantor.
|X| < |℘ (X)|
14
Tema 2
Conceptos Básicos. Lenguajes.
Alfabetos, cadenas y Lenguajes.
Def: Se denomina Alfabeto ( ∑ ) a un conjunto finito y no vacío de
símbolos.
Ejemplos:
∑ = {0, 1} ∑ = {a}
∑ = {· , -} ∑ = {©, ®}
Si ∑ 1 y ∑ 2 son alfabetos, ∑ 1 ∪ ∑ 2 es un alfabeto.

Si ∑ 1 y ∑ 2 son alfabetos, ∑ 1 ∩ ∑ 2 es un alfabeto, siempre que
dicha intersección sea distinta del vacío,
Sea ∑ = {a, b, c}
a ∈∑
€∉∑
Def: Se denomina Cadena, palabra o frase a una secuencia finita de

símbolos de un alfabeto.
Ejemplos:
w=0101 w=aaaaa
w=· --· · -· w=©©
Teor: ∀ a∈ ∑ , a es cadena sobre ∑ .
¡Ojo!, Sea ∑ ={a, b}, ab ≠ ba
Def: |w| = Longitud de la cadena w

Ejemplos:
w = awañac, |w| = 6
w = a, |w| = 1
Def: Se define cadena vacía, y se denota por å (épsilon), aquella cuya

longitud sea 0.
å = Cadena vacía, | | = 0.
Def: Se define lenguaje formal al conjunto de cadenas sobre un

alfabeto.
Ejemplos:
Sea ∑ = {0, 1}
L 1 ={0, 1, 11, 1111} L 2 ={0,1}= ∑
15
L 3 ={0, 00, 000, 0000.......

L 4 ={ , 1, 10, 110,...}
L5 =∅
Teor: Un lenguaje SÍ puede ser vacío, como es el caso de L 5 .
Aclaración: { } ≠∅

Más ejemplos:
Sea ∑ = {x, *}
L 1 ={x} L 2 ={x****,x}
L 3 ={*,**,***,...
L4 =∅ L 5 ={ }
w∈L (pertenece al lenguaje)

ó
Si tenemos una cadena sobre ∑
w∉L (no pertenece al lenguaje)
Def: Dado ∑ , se llama lenguaje universal a ∑ *, o cierre de ∑ . Es el

lenguaje de todas las cadenas que puedo formar con ese alfabeto.
Ejemplo:
∑ = {a}, ∑ *={ , a, aa, aaa........}

Teor: Sobre cualquier ∑ , ∑ * es infinito.
Operaciones con cadenas.
Sean x, w∈ ∑ *,
• x· w = concatenación
Sea ∑ = {a, b, c}
a, b∈ ∑ , c∈ ∑ , ab· c = abc
|wx| = |w| + |x|

w = w=w, ∀ w∈ ∑ *

• w n = potencia
ε , si n = 0
wn = n −1 si n ≥ 1
w·w
Sea ∑ = {1,0}
w=010∈ ∑ *
16
(010) 0 =
(010)¹ = 010· (010) 0 = 010· = 010 = w

(010)² = 010· 010· (010)0 = 010· 010· = 010· 010=010010

Def: Una cadena es igual a otra sii tienen la misma longitud y los
símbolos en la misma posición.
Def: Se define un prefijo de la siguiente manera:

Sean x, w∈ ∑ *,
x es prefijo de w si w = x· y, si ∃ y∈ ∑ * | w = x· y
Teor: Toda cadena es prefijo de sí misma
Ejemplos:
Sea w=123,
Prefijos(w) = { å, 1, 12, 123}
Def: Se llaman prefijos propios aquellos que no son iguales a la cadena
Def: Se define subcadena de la siguiente manera:

Sea w∈ ∑ *,
x∈ ∑ * es subcadena de w si w = zxy, ∃ z, y∈ ∑ *|w = zxy
Teor: es subcadena de toda cadena.
Ejemplos de subcadenas:
Sea w = 123,
Subcadenas sobre w: 1, 2, 3, 12, 23
¿Cuántas subcadenas se pueden formar con una cadena?
s = 1 + 2 + 3 + ... + m
s = m + m-1 + ... + 1_
2s = (m + 1) + ( m + 1)+...+( m + 1)
Porque
es subcadena de toda cadena
m(m + 1)
2s = (m + 1)· m ⇒ s = +1
2
Def: Se define una subsecuencia de una cadena como una

combinación de símbolos de dicha cadena en orden, pero no
tienen que ser consecutivos.
P.ej.:
w = abcre; Subsecuencias: "ace", "abre", "acre", "bre", "are"...
El número de subsecuencias que se pueden formar con una

cadena es de 2 n
17
Def: Se define la inversa o traspuesta de una cadena como:
ε si w =
wi = i

 y a si w = ay (a ∈ ∑ , y ∈ ∑ *)
P.ej.:
(arroz) i = (rroz) i a = (roz) i r = (oz) i rra = (z) i orra =
i
zorra = zorra
Operaciones con lenguajes.

Sean L 1 , L 2 lenguajes sobre ∑ .
L1 , L 2 ⊆ ∑ *
Concatenación: L 1 · L 2 = { xy∈ ∑ *| x∈L 1 ∧ y∈L 2 }
P.ej.:
L 1 = {0, 1}
L 2 = {a, b, cd}
L 1 · L 2 ={0a, 0b, 0cd, 1a, 1b, 1cd}
Potencia:
Sea L ⊆ ∑ *,
å si n = 0
L n =  n−1
 L·L si n ≥ 1
P. ej.:
L = {0, 1}
L0 = { } ≠ ∅
L¹ = L· L 0 =L· { }=L={0, 1}

L² = L· L¹=LL={00, 01, 10, 11}

L 5 = Números binarios de 5 bits
Teor: Todo alfabeto es un lenguaje

Teor: ∅ 0 ={ }
Teor: ∅ x = ∅, ∀x ≥ 1
Sean L 1 , L 2 ⊆ ∑ *,
L 1 ∪ L 2 = {x∈ ∑ * | x∈L 1 ∨ x∈L 2 }
L 1 ∩ L 2 = {x∈ ∑ * | x∈L 1 ∧ x∈L 2 }
Def: L 1 es sublenguaje de L 2 si L 1 ⊆ L 2
Teor: Todo lenguaje L sobre ∑ es L ⊆ ∑ *
18
Teor: Dos lenguajes son iguales si tienen todos sus elementos iguales
Teor: Sean L 1 , L 2 ,L 3 ⊆ ∑ *,
L 1 (L 2 ∪ L 3 )=L 1 L 2 ∪ L 1 L 3
(L 1 ∪ L 2 )L 3 =L 1 L 3 ∪ L 2 L 3
Def: Se define el Cierre de Kleene (o cierre estrella) de este modo:
∞
i 0
∪ L¹ ∪ L² ∪ L³ ∪ .... Por eso existe ∑ *
L*=
ΥL = L
i =0
Def: Se define el Cierre Positivo de este modo:
∞
L+=
Υ L = L¹ ∪ L² ∪ L³ ∪ ....
i
i =1
Teor: L+ = L* - { }
Complementación:
Sean L 1 , L 2 ⊆ ∑ *,
L 1 - L 2 = { x∈ ∑ * | x∈L 1 ∧ x∉L 2 }
__
∑ * - L = L = { x∈ ∑ * | x∈ ∑ * ∧ x∉L}
Teor: A+ = AA* = A*A
Teor: (A*)* = A*
Teor: (A+)+ = A+
Expresiones regulares.
1) ∅ es Expresión regular
2) es Expresión regular

3) ∀ a∈ ∑ , a es Expresión regular
4) Si r 1 y r 2 son expresiones regulares ⇒ r 1 · r 2 , r 1 | r 2 , r* son E.R.
5) Ninguna otra secuencia de métodos es Expresión regular.
Teor: Toda expresión regular representa un lenguaje regular
r L(r) Lenguaje representado

∅ ∅

a {a}
r1· r 2 L(r 1 )· L(r 2 )
19
r1 | r 2 L(r 1 ) ∪ L( r 2 )
r1* L(r 1 )*
Inversa:
Sea L ⊆ ∑ *,
L i ={w∈ ∑ * | w i ∈L}
P.ej.:
L 1 ={abra, cadabra}
L i ={arba, arbadac}
20
Tema 3
Lenguajes Regulares y Autómatas
Finitos.
Expresiones Regulares.
Tiene que ser finito

L⊆ ∑ * ó
Tiene que ser infinito enumerable (|L|=|N|)
P.ej.:
∑ ={d, c, z}
∑ *={ ,d,c,z,dd,dc,dz,cd,cc,cz,zd,zc,zz......

∑ *≅ Ν
Teor:
℘(∑ *) ≅ 2 Ν 
 Ningún método de especificación determinará TODOS los
| N |< 2 Ν 
lenguajes sobre un alfabeto.
Ejemplo de expresión no regular:

{b i , i ≥ 0}={ , b, bb, bbb, bbbb....... } = b*

Sin embargo, p.ej.:

{a i b j | i, j ≥ 0} = { , a, b, ab, aab, abb,.....}

Sí es regular, porque se puede hacer concatenando algunos lenguajes.

En este caso sería por ej:
L 1 ={a}, L 2 ={b}, L 1 *· L 2 * = a*b*, que demuestra que es regular.
Teor: Sean r, s expresiones regulares.

r = s ⇔ L(r) = L(s)
Teor: Puede que hayan varias expresiones regulares que representan el

mismo lenguaje.
P. ej.:
(a*b)*= |(a|b)*b
L( |(a|b)*b)={ , ab, b, aab, ababab.... }

Teor: Órden de precedencia entre operadores
*
·
|
21
Notación: r| å = r? El signo de interrogación significa que puede que r esté o no
Equivalencias entre expresiones regulares.
r|s=s|r r(s|t)=rs|rt
r| ∅ = ∅ |r=r (r|s)t=rt|st
r|r=r r*=r**=r*r*=( |r)*=r*(r| )= |rr*

r | (s | t) = (r | s) | t (r|s)*=(r*|s*)*=(r*s*)*
r = r=r
r(sr)*=(rs)*r
r ∅ = ∅ r= ∅ (r*s)*= å|(r|s)*s
(rs)t=r(st)
Ejercicios:
Describir con palabras qué lenguaje representan las siguientes expresiones regulares:
Expresión regular Descripción

0* Cadenas de ceros de cualquier longitud
(0|1)* Cadenas binarias de 0 y 1 de cualquier longitud
(10)* Cadenas binarias donde cada 1 va seguido de un 0, ó es
(0|1)*1(1|0)* Cadenas binarias con al menos un 1

(1|10)* Cadenas binarias que no tienen 2 ceros consecutivos, ó es
1(0|1)*1 Cadenas binarias que empiezan y terminan en 1

1*01*01* Cadenas binarias que tienen dos ceros
(0|1)*00(1|0)* Cadenas binarias que tienen la subsecuencia 00
Dada la descripción del lenguaje, encontrar una expresión regular equivalente.

(Se supone ∑ ={0, 1})
Cadenas binarias que acaben en 0 (1|0)*0

Cadenas con sólo un 0 1*01*
Cadenas binarias que no contienen "000" ((1*|0)(1*|0)1)*
Cadenas que si tienen un 1 va precedido y seguido de un 0 0*(010)*0*
Def: Un conjunto es cerrado con respecto a la operación # si:

∀ x, y∈C, x#y∈C
Ejemplos:
Ζ * este conjunto es cerrado respecto a la multiplicación
Ζ / este conjunto no es cerrado respecto a la división
Conclusión de la parte: El conjunto de los lenguajes regulares es el menor conjunto

cerrado respecto a las operaciones: Unión, intersección, concatenación,
complementación y cierre de Kleene, y que contiene el ∅ y los lenguajes unitarios.
Aparecen en analizadores léxicos y en búsqueda de patrones.
22
Autómatas Finitos Deterministas (AFD, DFA).

Se define un Autómata Finito Determinista como una quíntupla del siguiente modo:
M ≡ ( ∑ , Q, F, q 0 , ä)
Descripción de cada uno de los elementos del autómata:
∑ → Como ya sabemos, es el alfabeto, en este caso el alfabeto del autómata
Q → Es el conjunto de estados del autómata. Q ≠ ∅ , ha de ser finito y
Q∩ ∑ =∅
F → F ⊆ Q, es el conjunto de estados de aceptación, o estados finales
q 0 → q 0 ∈Q, es el estado de arranque o inicial del autómata
ä → Es la función de transición del autómata. Viene definida como:
ä:Q × ∑  → Q
ä(q, a) = p
p, q ∈ Q
a∈ ∑
Aclaración: ä es una función, está definida para todos los pares Q × ∑
Estructura de un autómata.
a b c d e f g h i j k l m n o p…$
El autómata no puede Este es el procesador del

cambiar la cadena autómata. Decide qué hacer
q0 ante la entrada que se lee.
q5 q1
La flecha muestra en qué
estado (qQ) se encuentra el
q4 q2 autómata.
q3
Nota: El apuntador del autómata devuelve el estado en el que se encuentra,

que puede ser de aceptación o no. Si es de aceptación "acepto la
cadena", si no, "no acepto o rechazo la cadena".
23
Diagrama de transiciones de un autómata.

Sea ∑ ={a, b}, Q = {0, 1, 2}, q 0 =0, F = {2}, y δ viene definida así:
q i /δ a b
0 1 0
1 2 0
2 2 2
Se define el diagrama de transiciones de dicho autómata como un grafo dirigido, en el

que los estados se representan por nodos, las transiciones por flechas, de tal manera que
dicho grafo satisface la definición de la función de transición, δ .
En este caso, en el autómata la función δ sería:
δ (0, a) = 1, δ (0, b) = 0, δ (1, a) = 2, δ (1, b)=0, δ (2, a) = 2, δ (2, b)=2
Nótese que para todos los símbolos del alfabeto, existe una transición de algún estado.
Sabiendo esto, el anterior autómata quedaría representado así
b a, b
a
a
0 b
1 2
qi
El estado inicial se representa por
qj
Los estados finales se representarán por
qi a
qj
Las transiciones lo harán como: δ (qi, a) = qj ⇔
Def Se define un estado de absorción o muerte como aquel estado q∈Q, y

q∉F, que no tiene ninguna transición hacia ningún otro estado (opcionalmente, a
sí mismo puede tenerlos), únicamente hay transiciones que inciden en él. Es
decir, si δ (q, a) = ∅ , ó, δ (q, a) = q, ∀a ∈ ∑ .
24
P. ej.:
a, b
a a
0 1 2
b
b
a, b
Como vemos, el estado 3 no tiene ninguna transición, únicamente hay

transiciones que inciden en él. Además, 3∉F, luego 3 es un estado de muerte.
Cuando tenemos estados de muerte, se toma el convenio de no dibujarlos.
En este último autómata,
Si w = aaab ⇒ El autómata acepta la cadena, puesto que para en 2, que es

estado de aceptación.
Si w = bbba ⇒ El autómata rechaza la cadena, puesto que para en 3, que no es
un estado de aceptación.
Ejercicio
Hacer el autómata que reconozca este lenguaje: (a|b)aba*
a, b a b
0 1 2 3
En este diagrama de transiciones, se ve que se ha omitido un estado de muerte, porque

por ejemplo el estado 1 no tiene transición con el símbolo "b", y va a parar a dicho
estado de muerte. Igual pasa con el estado 2 y el símbolo "a", y el estado 3 con el
símbolo "b"
Ejercicio
Hacer el diagrama de transiciones con esta definición del autómata:
Q={0,1,2,3} q i /δ a b
∑ ={a, b}
0 0 1
q 0 =0
1 0 2
F={0, 1, 2} 2 0 3
3 3 3
25
a,b
b
b b
0 a 1 2 3
Como vemos, el estado 3 es un estado de muerte y podía haberse omitido.
Este autómata, por ejemplo, acepta combinaciones de cadenas que no tengan 3 "b"
seguidas.
Ejercicio
Q={q 0 ,q 1 } q i /δ 0 1
∑ ={0, 1} q0 q0 q1
F={q 0 } q1 q1 q0
q 0 =q 0
0 0
1
q0 1 q1
Teor: Los lenguajes reconocidos por los DFA son los lenguajes regulares
Ejercicio.
Suponiendo ∑ ={0, 1}, dibujar los diagramas de transición que reconozcan:
a) Cadenas terminadas en 00
b) Cadenas con dos "unos" consecutivos
c) Cadenas que no contengan dos "unos" consecutivos
d) Cadenas con dos "ceros" consecutivos o dos "unos" consecutivos
e) Cadenas con dos "ceros" consecutivos y dos "unos" consecutivos
f) Cadenas acabadas en 00 o 11
g) Cadenas con un "uno" en la antepenúltima posición
h) Cadenas de longitud 4.
26
a)
1 0
0
0
A 1
B C
1
b)
0 0, 1
1
1
A 0
B C
c)
0
1
1
A 0 B M
d)
1
1 B D
A 0 1
0
C 0
E
e)
0,1
0
1 0
1 B C D E
1
A 0 1
0,1
0
1
F 0
G H 1
I
0
27
f)
1
0 1
0 0 1 1
A B C D E
0
1 0
g)
0
1 0,1 0,1
A B C D
h)
0,1 0,1 0,1 0,1
A B C D E
Def: Sea M ≡ ( ∑ , Q, F, q 0 , δ ), con p, q ∈Q, se definen estados equivalentes,

y se denota por p ≡ q ⇔ ∀ w∈ ∑ *, δ (p, w) ∩ F ≠ ∅ ⇔ δ (q, w) ∩ F ≠ ∅ , es
decir,si los dos estados se comportan igual ante todas las cadenas de ∑ *.
Def: Se dice que r, s∈Q son distinguibles, si ∃ w∈ ∑ *| δ (r, w)∈F ∧ δ (s, w)∉F.
Algoritmo de Reducción de estados de un DFA.

Este algoritmo nos permitirá minimizar el número de estados de un DFA de tal manera
que el funcionamiento antes y después de minimizar sea el mismo. Se parte de un
conjunto llamado π 0 , que contendrá a su vez dos conjuntos, uno que será Q - F y otro
que será F, es decir:
π 0 = {F, Q-F}
Los sucesivos pasos π i , con i>0, se conseguirán de la siguiente manera:
Hay que coger los distintos símbolos pertenecientes a∈ ∑ , y mirar a dónde transita cada
estado de cada cada uno de los conjuntos. Si algún estado q∈ Q transitase con dicho
símbolo a otro conjunto, éste se separa en un conjunto distinto, y se vuelve a aplicar
28
dicho algoritmo. Si hubiera un conjunto cuyo cardinal fuera uno (es decir, tiene un
elemento), no hace falta comprobar con él las transiciones, puesto que éste no puede
cambiar. Si en algún paso del algoritmo, dos o más estados de un mismo conjunto
transitasen a un mismo conjunto distinto del que están, esos estados se separan en un
conjunto nuevo. El orden en que se aplican los a∈ ∑ puede ser arbitrario. El algoritmo
para una vez que no hayan cambios con NINGUNO de los a∈ ∑ , es decir, con ningún
símbolo del alfabeto. Los estados equivalentes serán aquellos que pertenezcan a un
mismo subconjunto de π n , siendo π n el último paso.
Ejemplo:
C
b
a
b
A a
B D b
E
a
a a
Se supone ∑ ={a, b}.
π 0 = {F, Q-F} = {{E}, {A, B, C, D}}

Si elegimos "a" como símbolo del alfabeto, no hay cambios, puesto que no hay
ningún elemento de Q que transite a uno de F, ni viceversa. Probemos ahora con la "b".
Con la "b" vemos que el estado D, transita a E, que es de aceptación y está en un

conjunto distinto al de los Q. Separamos dicho estado en uno distinto.
π 1 ={{E},{A, B, C}, {D}}

Igualmente con el símbolo "a" ahora no hay cambios, sin embargo con la "b", vemos
que el estado B transita a D, que está en otro conjunto. Lo separamos.
π 2 ={{E}, {A, C}, {B}, {D}}
Ahora ni probando con la "a" ni con la "b" vemos que haya cambio, con lo cual el
algoritmo termina. Llegamos a la conclusión de que los estados A y C son estados
equivalentes. El diagrama de transiciones queda pues así:
29
b
b
{A,C}
a
B D b
E
a
a a
Otro ejemplo:
1
a b
a
b
b
0 2
a
b b
3 b
4
a
π 0 ={{0, 1, 2, 4}, {3}}
El estado 0 con la "b", transita a 3, y el 1 igual, luego los separamos en un conjunto

distinto.
π 1 ={{0,1}, {2,4}, {3}}
Si cogemos la "a" como símbolo, vemos que el estado 2 transita al estado 1, mientras
que 4 con el mismo símbolo transita a 4, luego los separamos.
π 2 ={{0,1},{2},{4},{3}}
Vemos que el estado 0 con la "a" va al estado 1, que está en el mismo conjunto, y el
estado 1 hace lo mismo; y el estado 0 con la "b" va al estado 3, y el estado 1 hace lo
mismo. Por tanto, no hay cambios y el autómata mínimo se obtiene uniendo los estados
0 y 1, y nos queda un autómata de 4 estados.
Teor: Si tenemos 2 DFAs, M 1 y M 2 , M 1 ≡ M 2 ⇔ L(M 1 )=L(M 2 )
30
Autómatas Finitos No Deterministas (FND, NFA).

Los NFAs son un superconjunto de los DFAs, es decir, la relación que hay entre DFA y
NFA es que los DFAs son un caso particular de los NFAs.
Cuando tenemos más de una transición con un mismo símbolo del alfabeto desde un
estado, hablamos de NFA.
Dibujo ilustrativo:
0 a
1 b
2
a
b
b
3 4
El estado 0, para el símbolo "a" tiene dos transiciones, una al estado 1 y otra al estado 4,
es decir, δ (0, a) = {1, 4}
Teor: En los NFAs no existen los estados de muerte o absorción.
Def: Se define un NFA de la siguiente manera:

M ≡ ( ∑ , Q, F, q 0 , δ )
Los elementos ∑ ,Q, F, q 0 , se definen igual que en los DFAs, lo que

cambia es la función de transición, δ .
Partes de Q
δ : Q× ∑  → ℘ (Q)
δ (q, a) ⊆ Q
∅ ∈℘(Q )
Aclaración: 
Q ∈℘(Q)
En el ejemplo ilustrativo de antes:

Q={0,1,2,3,4} q i /δ a B
F={2,3,4}
0 {1, 4} {3}
∑ ={a, b}
1 {1} {2}
q 0 =0
2 {∅ } {∅}
3 {∅ } {∅}
4 {∅ } {4}
31
Teor: Si tenemos un NFA M ≡ ( ∑ , Q, F, q 0 , δ ),

L(M)={w∈ ∑ * | δ (q 0 , w) ∩ F ≠ ∅ }
Es decir, el autómata acepta aquellos lenguajes en los que al procesar la
cadena se obtenga un conjunto en el que haya al menos un estado de
aceptación.
Ejemplo:
0,1 0,1
0 0
1 0
2
1
3
1
4
0,1
Sea por ejemplo w = 01001, suponiendo que ∑ ={0, 1}
δ (A, 0) = {A, D}
δ ({A, D}, 1) = δ (A, 1) ∪ δ (D, 1) = {A, B} ∪ ∅ = {A, B}
δ ({A, B}, 0) = {A, D} ∪ ∅ = {A, D}
δ ({A, D}, 0) = {A, D, E}
δ ({A, D, E}, 1) = {A, B, E}
¿Se acepta la cadena? El último conjunto, {A, B, E} ∩ F= {E}, luego como {E} ≠ ∅ ,
esta cadena se acepta.
Teor: Sean M 1 y M 2 dos NFAs, M 1 ≡ M 2 ⇔ L(M 1 )=L(M 2 )
Teor: Siempre se puede convertir un NFA a DFA
Teor: Los NFAs reconocen los lenguajes regulares
32
Algoritmo de Conversión de un NFA a un DFA.

Teor: Dado un NFA M ≡ ( ∑ , Q, F, q 0 , δ ),
∃ DFA M' ≡ ( ∑' , Q ' , F ' , q 0' , δ ' ) | L(M) = L(M')
1) Q ' = ℘(Q )
2) ∑ = ∑ '
3) q '0 ={q 0 } (conjunto de estados que contiene el de arranque del NFA)
4) F' ⊆ Q' (aquellos subconjuntos de Q que contengan algún p∈F)
5) δ '({ q1 , q 2 , ... q k }, a) = {p 1 , p 2 ... p m } ⇔ δ ({q 1 , q 2 , ... q k }, a) = {p 1 ,
p 2 ... p m }
Para construír un DFA a partir de un NFA, se procede del siguiente modo:

Se toman todos los símbolos de ∑ , y se aplica δ sobre el símbolo inicial, q 0 . Al hacer
eso, darán como resultado un conjunto A ∈℘(Q), que añadiremos a una lista de Estados
nuevos. Se denomina marcar un estado a aplicar la función δ sobre todos los símbolos
del alfabeto. A partir de ahí hay que marcar todos los estados nuevos que nos salgan. El
algoritmo para una vez estén marcados todos los estados nuevos. Serán estados de
aceptación aquellos estados que contengan algún estado de aceptación del NFA. Por
último se dibuja el diagrama de transiciones.
Ejemplo:
Pasar a DFA este NFA
0 a
1
a
a
2 3
b
∑ ={a, b}, q 0 =0
Empezamos aplicando δ sobre el símbolo inicial Estados nuevos
δ ({0}, a) = {1, 2} Este conjunto no lo teníamos, se añade a la lista → {1, 2}
δ ({0}, b) = { ∅ } {∅}
Ahora hay que marcar estos estados, y ver si salen estados nuevos. {3}
δ ({1, 2}, a) = { ∅ } {2}
δ ({1, 2}, b) = {3} No estaba, lo añadimos
δ ({ ∅ }, a) = δ ({ ∅ }, b) ={ ∅ }
δ ({3}, a) = {2}
δ ({3}, b) = { ∅ }
δ ({2}, a) = { ∅ }
δ ({2}, b) = {3}
33
Ya tenemos todos los estados marcados, ahora ya sólo queda pintar el diagrama de
transiciones, luego el DFA quedaría así:
{1,2} b
a {3}
b
{0} a
a {2}
b
b
a
{∅}
a,b
Como podemos apreciar, { ∅ } es un estado de muerte, con lo cual en una reducción de

estados posterior se podría quitar.
NFAs con épsilon-transiciones.

Se puede definir un NFA con épsilon-transiciones (NFA-ε) como:
M ≡ (Σ, Q, F, q 0 ,δ), donde únicamente varía la función δ con respecto de los NFAs,
estando definida del siguiente modo:
ä: Q × (Σ ∪ {å}) 
→℘(Q )
Ejemplo ilustrativo
a
ε 1 2 ε
0 5 a
6
ε
ε
3 b
4
34
Como ya sabemos, ε representa una cadena vacía, es decir |w|=0, pero también se puede
definir como un símbolo que nos permite transitar a otro estado sin consumir símbolos.
A raíz de esto, se puede definir la ε-Clausura.
Def: Se define la ε-Clausura (ε-cl) como un conjunto de todos los estados a

los que se puede acceder desde un estado q∈Q sin consumir símbolos
de la entrada.
ε-cl={p∈Q | p es accesible o alcanzable desde q sin consumir símbolos de la

entrada}
P.ej.:
En el anterior diagrama de transiciones,
-cl(0) = {0, 1, 3}

-cl(2)={2, 5, 0, 1, 3} = {0, 1, 2, 3, 5}

-cl({1, 4})= -cl(1) ∪ -cl(4) = {1} ∪ {4, 5, 0, 1, 3} = {0, 1, 3, 4, 5}

Teor: q∈ -cl(q), ∀ q. Es decir, la -cl nunca puede ser vacía, contendrá al

menos el estado sobre el que se aplica la -cl, a menos que sea la
-cl({ ∅ }), porque -cl({ ∅ })={ ∅ }

Sea r∈Q,
δ (r, a) =
Υδ ( q , a )
q∈R
δˆ (q, )= -cl(q)

δˆ (q, aw)= ∪ r∈ δ ( -cl(q), a)
a∈ ∑ , w∈ ∑ *
δˆ (r, a)=
Υδ (q, a)
q∈R
En general, δ ≠ δˆ .
Teor: Si tenemos un NFA- , M ≡ ( ∑ , Q, F, q 0 , δ )

L(M)={w∈ ∑ *| δˆ (q 0 , w) ∩ F ≠ ∅ }
Ejemplo:
ε b
1 2 6
5
a ε
3 b 4 ε
6
35
Para saber si w∈L(M), se procede haciendo la -cl del símbolo inicial. Posteriormente

al conjunto conseguido al aplicar dicha clausura, se aplica la función δ sobre el primer

símbolo de la cadena, posteriormente se aplica la
-cl y se vuelve a aplicar δ sobre el siguiente símbolo de la cadena. Estos dos últimos
pasos se repiten hasta que se evalúen todos los símbolos de la cadena. Si en el conjunto
obtenido haciendo la última -cl hubiera algún estado de aceptación, la cadena se

acepta, si no, se rechaza.
Sea w = a, |w| = 1
δˆ(0, w)= δ (0, a)
-cl(0) = {0, 1} ( -cl del símbolo inicial)

δ ({0, 1}, a)={3}

-cl({3})={1, 3}
{1, 3} ∩ F = ∅ , luego la cadena se rechaza.
Sea ahora w=ab, |w|=2

-cl(0) = {0, 1} ( -cl del símbolo inicial)

δ ({0, 1}, a)={3}

-cl({3})={1, 3}
δ ({1, 3}, b)={2, 4}

-cl({2, 4})={2, 4, 5}
{2, 4, 5} ∩ F ≠ ∅ , luego acepta la cadena.
Algoritmo de paso de NFA con ε-transiciones a DFA.

Para pasar un NFA- a DFA, se sigue el siguiente algoritmo:

Para empezar, se hace la -cl del símbolo inicial, esto nos dará un conjunto, al que

llamaremos, por ejemplo, S. Hay que marcar (véase def. en pág. 34) ese estado con los
símbolos del alfabeto. A partir de aquí, cada vez que al marcar cada uno de los símbolos
nos salga un conjunto que aun no tiene nombre, se aplica la -cl sobre éste, se le da un

nombre, y se vuelve a marcar. Se considerarán estados de aceptación aquellos conjuntos

que contengan algún estado de aceptación del NFA- inicial. El algoritmo para una vez

estén marcados todos los estados nuevos de dicho autómata.
36
a
ε 2 3 ε
ε ε
0 1 ε 6 7
ε
4 b
5 a
ε
8
b
10 b
9
∑ ={a, b}

-cl(0)={0, 1, 2, 4, 7} = S ( -cl del símbolo inicial)

Ahora marcamos este nuevo estado

δ (S, a)={3, 8}
δ (S, b)={5}
Ambos son conjuntos que aún no tienen nombre, hacemos sus -cl
-cl({3, 8})={1, 2, 3, 4, 6, 7, 8} = B

-cl({5})={1, 2, 4, 5, 6, 7} = C
Marcamos dichos conjuntos
δ (B, a)={3, 8} Este ya lo teníamos, es B, luego no hace falta volver a hacer
su -cl.

δ (B, b)={5, 9} No lo tenemos, haremos su clausura.

δ (C, a)={3, 8}=B
δ (C, b)={5}=C

-cl({5, 9})={1, 2, 4, 5, 6, 7, 9}=D

δ (D, a)={3, 8}=B
δ (D, b)={5, 10} No está, hay que hacer su clausura.

-cl({5, 10})={1, 2, 4, 5, 6, 7, 10}=E

δ (E, a)={3, 8}=B
δ (E, b)={5}=C
Hemos terminado, ya que todos los estados están marcados.

E será el único estado de aceptación ya que es el único que contiene el estado 10, que
era el estado de aceptación del NFA- .
Ahora ya sólo queda hacer el diagrama de transiciones:
37
C
b
b
a
a
b
a b
S B a D E
Def: Se dice que un estado q∈Q es importante si se da al menos una de

de estas dos reglas:
1) q∈F
2) ∃ a∈ ∑ | δ (q, a) ≠ ∅
P. ej., estados importantes del ejemplo anterior={2, 4, 7, 8, 9, 10}
Algoritmo de paso de NFA con ε-transiciones a NFA sin

ε-transiciones.
Teor: Dado un M NFA- M ≡ ( ∑ , Q, F, q 0 , δ ), ∃ NFA M'≡ ( ∑ , Q, F', q0 , δ ') |

L(M) = L(M')
F' = F∪ {q∈Q | -cl(q) ∩ F ≠ ∅ }

δ ', ∀a ∈ ∑, δ '(q, a) = δˆ(q, a )
En este algoritmo se trata de aplicar la función δˆ a cada estado con todos los símbolos
a ∈ ∑ . Cuando al aplicarla obtengamos un conjunto con n estados, significa que desde el
estado al que estamos haciendo la δˆ, debemos poner una transición a cada uno de esos
n estados que hemos obtenido al final.
Nota: δˆ(q, a) = -cl( δ ( -cl(q), a))

q∈Q
a∈ ∑
38
Ejemplo
0 1 2
ε ε
A B C
∑ ={0, 1, 2}
· δˆ(A, 0) = -cl( δ ( -cl(A), 0)) = -cl( δ ({A, B, C}, 0)) = -cl(A)={A, B, C}

Nota: Esto significa que desde el estado A, con el símbolo 0, hemos de añadir
en el diagrama nuevo una transición a A, otra a B y otra a C
· δˆ(A, 1) = -cl( δ ( -cl(A), 1)) = -cl( δ ({A, B, C}, 1)) = -cl(A)={B, C}

· δˆ(A, 2) = -cl( δ ( -cl(A), 2)) = -cl( δ ({A, B, C}, 2)) = -cl(A)={C}

· δˆ(B, 0) = -cl( δ ( -cl(B), 0)) = -cl( δ ({B, C}, 0)) = -cl( ∅ )= ∅

· δˆ(B, 1) = -cl( δ ( -cl(B), 1)) = -cl( δ ({B, C}, 1)) = -cl(B)={B, C}

· δˆ(B, 2) = -cl( δ ( -cl(B), 2)) = -cl( δ ({B, C}, 2)) = -cl(C)={C}

· δˆ(C, 0) =
-cl( δ (
-cl(C), 0)) =
-cl( δ ({C}, 0)) = -cl( ∅ )= ∅

· δˆ(C, 1) = -cl( δ ( -cl(C), 1)) = -cl( δ ({C}, 1)) = -cl( ∅ )= ∅

· δˆ(C, 2) = -cl( δ ( -cl(C), 2)) = -cl( δ ({C}, 2)) = -cl(C)={C}

Serán estados de aceptación aquellos estados que lo fueron en el NFA- , y además
todos aquellos cuya -cl contenga algún estado de aceptación de ese NFA- , en este

caso los tres estados serán de aceptación. El diagrama del NFA sin -transiciones queda
como sigue:
0, 1, 2
0 1 2
0, 1 1, 2
A B C
39
Construcción de Thompson.
Este algoritmo nos permite convertir una expresión regular en un NFA- . Para ello, se
siguen las siguientes reglas:
Sean α , β expresiones regulares.
Expresión Regular Autómata finito
a
a∈ ∑
(α )
α |β
(β )
(α )
(β )
α· β
(α )
α*

40
Ejemplo:
Sea α =ba*
a
0 1
b
2 3
a* (nótese que en este paso el estado 1 deja de ser de aceptación)
a
0 1
ε ε
4 ε
5
b· a*
ε
Concatenación
a
0 1
ε ε
2 b
3 ε
4 ε
5
Otro ejemplo:
α =01|1*
41
0· 1 (En este paso haremos directamente la concatenación, que es entre los

estados B y C)
A 0
B ε
C 1
D
1*
ε
1
F G
ε ε
E ε
H
01|1*
A 0
B ε
C 1
D
ε ε ε
I F
1
G J
ε ε
ε ε
E ε
H
Paso de NFA a Expresión Regular (Lema de Arden).

Al igual que es posible pasar de expresión regular a NFA, como hemos visto con el
algoritmo de Thompson, es posible hacer el paso contrario, es decir, pasar de NFA a
Expresión Regular. La descripción es así:
Sea un NFA M ≡ ( ∑ , Q, F, q 0 , δ ). Sea q i ∈ Q ,

A i ={w ∈ ∑ *| δ ( q i , w) ∩ F ≠ ∅ } (se definen así las cadenas aceptadas por q i )
Hay 3 reglas:
1) A 0 =L(M)
2) Es posible que A i = ∅
3) Si q i ∈F, ε ∈ Ai
42
Ejemplo:
a b
0 1 2
a
a, b
b
5 a, b
b
3 a
4
A 0 = aA 1 ∪ bA 3
A 1 = aA 5 ∪ bA 2
Regla 3, Si q i ∈F, ε ∈ Ai , es decir, como es
A 2 = aA 5 ∪ bA 5 ∪
de aceptación, se añade

A 3 = aA 4 ∪ bA 5

A 4 = aA 5 ∪ bA 5 ∪
A5=∅
Como se dice en la Regla 1, el objetivo de estos sistemas es despejar A 0 , lo que nos

dará la expresión regular del NFA.
Como A 5 = ∅ ,
A 4 = aA 5 ∪ bA 5 ∪ =a ∅ ∪ b ∅ ∪ = ∅ ∪ ∅ ∪
=
A 3 = aA 4 ∪ bA 5 = a ∪ b ∅ = a

A 2 = aA 5 ∪ bA 5 ∪ = A 4

A 1 = aA 5 ∪ bA 2 = a ∅ ∪ b = b
A 0 = aA 1 ∪ bA 3 = ab ∪ ba.
Luego, como vemos, efectivamente L(M)=(ab|ba)
Otros ejemplos de esta técnica
0 b
1
En este ejemplo,
A 0 =aA 0 ∪ bA 1
A1=
43
Luego, A 0 =aA 0 ∪ b = aA 0 ∪ b
???
En principio este sistema nos ha dado una expresión sin solución, ya que la función A 0
depende de sí misma. Estos casos tienen una única solución, y se aplica el llamado
Lema de Arden.
Teor: Lema de Arden

X=AX ∪ B, donde ∉A, tiene como única solución X=A*B

Con este lema, podemos afirmar que en el anterior ejemplo A 0 = aA 0 ∪ b, la solución

es: A 0 =a*b, luego L(M)=L(a*b)
Dem: Demostración del Lema de Arden.
!
X = AX ∪ B ⇔ X=A*B
⇐ ) X=A*B=(A+ ∪ )B=A+B ∪ B=AA*B ∪ B=A(A*B) ∪ B, con lo cual X=A*B

⇒ ) La solución es única. Haremos esta parte por reducción al absurdo.

Sup. que X=A*B ∪ C es solución con A*B ∩ C = ∅
X = AX ∪ B
A*B ∪ C = A(A*B ∪ C) ∪ B =AA*B ∪ C ∪ B = A+B ∪ AC ∪ B =A+B ∪ B ∪ AC =
(A+ ∪ )B ∪ AC = A*B ∪ AC.

Con lo cual vemos que A*B ∪ C = A*B ∪ AC
C ∩ (A*B ∪ C)=C ∩ (A*B ∪ AC)
C = C ∩ AC ⇒ C ⊆ AC

∉A. Es absurdo, la cadena más corta de AC ha de ser más larga que la cadena más
corta de C. Esto sólo es posible si C = ∅ , con lo cual hemos llegado al absurdo por
suponer que había otra solución que no fuese X = A*B, con lo cual ésta es única.
Otro ejemplo
a b
0 a
1 a
2 a
3 b
4
A 0 =aA 1
A 1 =aA 2 ∪ bA 4
44
A 2 =aA 3 ∪ bA 4
A 3 =aA 3 ∪ bA 4 ∪ ε
A 4 =bA 4 ∪ ε
Solución:
Arden
A 4 = bA 4 ∪ ε = b* = b*

A 3 = aA 3 ∪ bA 4 ∪ ε = aA 3 ∪ (bb* ∪ ε ) = aA 3 ∪ b* = a*b*
A 2 = aA 3 ∪ bA 4 = a(a*b*) ∪ bb* = a+b* ∪ b+
A 1 = aA 2 ∪ bA 4 = a(a+b* ∪ b+) ∪ bb* = aa+b* ∪ ab+ ∪ b+
A 0 = aA 1 = a(aa+b* ∪ ab+ ∪ b+) = aaa+b* ∪ aab+ ∪ ab+
Luego, L(M) = L(aaa+b* ∪ aab+ ∪ ab+)
Lema: Sea M un Autómata Finito, ∃ una E.R. r | L(M)=L(r).
Teor: Teorema de Kleene

Un lenguaje es regular sii es aceptado por el
autómata finito.
Lema del Bombeo (Pumping Lemma).

Este lema nos permitirá demostrar que un lenguaje no es regular.
1) w = xyz
2) | xy |≤ n

∀ L ⊆ ∑ *, ∃ n∈Ν | si w∈ ∑ *, w∈L con |w| ≥ n ⇒ 
3) | y |≥ 1
4) xy y z ∈ L, ∀k ∈ N
Teor: Si un lenguaje cumple el lema del bombeo, PUEDE que sea regular y
puede que no. Si un lenguaje no lo cumple, entonces es únicamente
cuando podemos afirmar que no es regular.
Ejemplo de lenguaje no regular
Dem:
L={a m b m | m ≥ 0}
Sea n∈Ν
(Nota: ¡n no se debe concretar!)
Sea w = a n b n .
45
(Nota: Hay que tener mucho cuidado con elegir la cadena)
|w| = 2n ≥ n.
Si w∈L, ha de ocurrir:
1) w = xyz
2) |y| ≥ 1
3) |xy| ≤ n
4) xy k z ∈L, ∀ k∈Ν
Si |xy| ≤ n ⇒ y sólo contiene símbolos "a", sea entonces y=a s , si |y| ≥ 1 ⇒ s ≥ 1
w= a n b n =,aaa...a, ,bbb...b,=xyz
n n
Entonces sea x = a , y = a s , y por tanto z = a n −( r + s ) b n
r
Sea k = 2, luego xy²z = a r a 2 s a n −( r + s ) b n = a n+ s b n . Como s ≥ 1 ⇒ xy²z∉L
Con lo cual, L no es regular.
Otro ejemplo.
Dem:
2
Sea L = {a i | i ≥ 1}
L = {aa, aaaa, aaaaaaaaa, aaaaaaaaaaaaaaaa, ...}
Sea n∈Ν
2
Sea z∈L; z = a n ; |z| = n² ≥ n, ∀ n.
1) z = uvw
2) |v| ≥ 1
3) |uv| ≤ n
4) uv r w∈L, ∀ r∈Ν
Si |uv| ≤ n ⇒ |v| ≤ n, con lo cual si |v| ≥ 1, 1 ≤ |v| ≤ n
n ≤ n² = |uvw|<|uv²w| ≤ n²+n < n²+2n+1=(n+1)²
Si r=2, n²<|uv²w|<(n+1)² ⇒ uv²w∉L, al estar entre dos cuadrados perfectos
Luego, L no es regular.
Teor: Sea M un autómata finito con k estados. L(M) es distinto de vacío si y

sólo si M acepta una cadena de longitud menor que k.
Teor: Sea M un autómata finito con k estados. L(M) es infinito si y sólo si M
46
acepta una cadena de longitud m con k ≤ m<2k
__
Teor: Sea L ⊆ ∑ *, si L es regular ⇒ L es regular.
Teor: Si L 1 y L 2 son regulares ⇒ L 1 ∪ L 2 es regular
Teor: Si L 1 y L 2 son regulares ⇒ L 1 ∩ L 2 es regular
Teor: Si L 1 y L 2 son regulares ⇒ L 1 · L 2 es regular
Teor: Si L es regular ⇒ L* es regular
47
Tema 4
Gramáticas. Lenguajes
independientes del contexto.
Gramáticas.
Def: Una gramática es una cuaterna formada de la siguiente manera:
G ≡ (V, ∑ , S, P)
∑ es el alfabeto, o también llamado conjunto de símbolos terminales, se

representan por letras minúsculas
V ≠ ∅ , V ∩ ∑ = ∅ es el conjunto de símbolos no terminales, se
representan por letras mayúsculas
S es el símbolo de arranque, S∈V
P es el conjunto de producciones de la gramática
P ⊆ V × ( ∑ ∪ V)*
Estas producciones se representan del siguiente modo
X → a, con X∈V, a∈ ∑ , y se lee, "X produce a"
Ejemplo:
1) E → E + E
2) E → E * E
3) E → (E)
4) E → a
S=E
V={E}
P={1), 2), 3), 4)}
∑ ={+, *, (, ), a}
Ej. Encontrar alguna manera de llegar a w=a*(a+a) con la anterior gramática.
E * E
a ( E )
E + E
a a
Vemos que los nodos hoja corresponden a lo que nos pedía el ejercicio, luego eso sería
una manera de llegar a la cadena w.
48
La anterior gramática también se puede escribir del siguiente modo:
E → E+E | E*E | (E) | a
Teor: Las producciones son reglas de reescritura, secuencias de derivaciones
Def: Se define una derivación del siguiente modo:

Sea α A β
Sea por ejemplo, α = abBcDdE, y β = abbcDDE

a∈ ( ∑ ∪ V)*
derivaen
Si (A → γ )∈P, αAβ ⇒ α γ β
P.ej:
n 1 n −1
α⇒β → α ⇒ γ ⇒ β

*
Notación: α ⇒ β se lee: α en una serie de derivaciones deriva en β .
Notación: Se entiende CFG como Context Free Grammar, con su equivalente

en castellano como Gramática independiente del contexto.
Teor: Dada una CFG, G

*
G ≡ (V, ∑ , S, P), L(G)={w ∈ ∑ * | S ⇒ w}
P. ej.:
En la gramática de antes:
E⇒a
E ⇒ (E) ⇒ (a)
E ⇒ (E) ⇒ ((E)) ⇒ ((a)) L(G)={a, (a), ((a)), a+a,....}
*
E ⇒ E+E ⇒ a+a
Ejemplos de gramáticas finitas
S→t
L(G)={t}
S → Sa
S ⇒ Sa ⇒ Saa ⇒ Saaa ⇒ Saaaa ...
L(G)= ∅ , ya que esta gramática nunca "para".
S → Sa | e
L(G)=ea*
49
Def: Una gramática es lineal por la derecha si es de la forma:

A → uB | v
A, B∈V
u,v ∈ ∑
Def: Una gramática es lineal por la izquierda si es de la forma:

A → Bu | v
A, B∈V
u,v ∈ ∑
Def: Una gramática es regular si es lineal por la izquierda o por la derecha.
P.ej.:
S → 0A
A → 10A |
L(G)=L(0(10)*)
Otro ej.:
S → S10|0
S⇒0
S ⇒ S10 ⇒ 010
S ⇒ S1010 ⇒ 01010
L(G)=L(0(10)*)
Teor: Dos gramáticas son equivalentes si los lenguajes que generan son el
mismo, es decir, G1 ≡ G2 ⇔ L(G1 ) = L(G2 ) . Vemos que esto ocurre en
los dos ejemplos anteriores.
Aclaración: Una autómata RECONOCE lenguajes, una gramática los GENERA.
Equivalencia entre gramáticas regulares y lenguajes

regulares.
Teor: Sea L regular ⇒ ∃ G | L(G) = L

Si L regular ⇒ ∃ DFA M | L = L(M)
M ≡ ( ∑ , Q, F, q 0 , δ )
V=Q
∑ = ∑
S = q0
P = {(q, ap) | δ (q, a)=p} ∪ {(q, å) | q∈F}
50
Ejemplo:
a
B a, b
b a, b
A C
El paso a gramática sería así:

V={A, B, C}
∑ ={a, b}
S=A
P:
A → aA | bB
B → aC | bC | (por ser de aceptación)
C → aC | bC
Teor: Dada una gramática regular, también se puede construir el autómata.

Dada G regular ⇒ ∃ NFA M | L(M)=L(G)
G ≡ (V, ∑ , S, P)
NFA, M ≡ ( ∑ , Q, F, q 0 , δ )
Q=V ∪ {f}, donde "f" es un estado nuevo

∑ =∑
F={f}
q 0 =S
La función δ se construye del siguiente modo:

Si A → (a1 a 2 ...a n B) ∈P ⇒ Q=Q ∪ { q1 , q 2 ...q n −1 }
Y construímos las transiciones:
δ (A, a1 a 2 ...a n )= δ ( q1 , a 2 a 3 ...a n )= ... = δ ( q n −1 , a n )=B
Interpretación gráfica:
q1 a2
q2 qn
a1 an
A B
51
Si A → (a1 a 2 ...a n ) ∈P ⇒ Q=Q ∪ { q1 , q 2 ...q n −1 }, y construimos transiciones:

δ (A, a1 a 2 ...a n )= δ ( q1 , a 2 a3 ...a n )= ... = δ ( q n −1 , a n )=f
Interpretación gráfica:
q1 a2
q2 qn
a1 an
A f
Def: Las gramáticas independientes del contexto son un caso particular de las
anteriores. Se definen así:
G ≡ (V, ∑ , S, P)
A→α
A∈V, α ∈( ∑ ∪V )*
P. ej.:
S → aSb | L(G)={a n b n | n ≥ 0}
Como vimos en el tema pasado, por el lema del bombeo demostramos
que no es regular, sin embargo ahora hemos dado una gramática que
genera este lenguaje, de lo cual concluimos que el conjunto de los
lenguajes independientes del contexto es un superconjunto del de los
regulares.
Lenguajes Independientes del contexto
Lenguajes regulares
Árboles de Análisis Sintáctico (AAS).

Los árboles de análisis sintáctico (AAS) son una representación gráfica de una
derivación.
Propiedades:
1) Nodo raíz = S 3) Nodos intermedios A∈V
52
2) Hojas: ∑ ∪ { }
P. ej.:
S → AB
A → aA | a
B → bB | b
Sea por ejemplo w = aabbb.

Con derivaciones podríamos llegar, por ejemplo, de este modo:
S ⇒ AB ⇒ aAB ⇒ aAbB ⇒ aabB ⇒ aabbB ⇒ aabbb
Con el AAS sería del siguiente modo:
A B
A A b B
a b B
Derivaciones más a la izquierda y derivaciones más a la

derecha.
En una gramática, se denomina "Derivaciones más a la izquierda" o "más a la derecha"
a susttuir el símbolo no terminal que está más a la izquierda, o derecha,
respectivamente.
Las derivaciones más a la izquierda se denominan Canónicas
No es situación normal que dada una cadena tenga siempre el mismo AAS.
P.ej.:
S → SbS | ScS | a
Sea w = abaca, vamos a hacerlo mediante derivaciones más a la derecha.
m.d . m.d . m.d . m.d . m.d .

S ⇒ ScS ⇒ Sca ⇒ SbSca ⇒ Sbaca ⇒ abaca
Como vemos, siempre se sustituye el símbolo que está más a la derecha hasta formar la
cadena, que es w.
53
El AAS sería del siguiente modo:
S c S
S b S a
a a
Vamos a hacerlo ahora con derivaciones más a la izquierda
m.i . m.i . m.i . m.i . m.i .

S ⇒ SbS ⇒ abS ⇒ abScS ⇒ abacS ⇒ abaca
El AAS queda así:
S b S
a S c S
a a
Como vemos, los AAS no son iguales.
Def: Se dice que una gramática es ambigua si una cadena tiene más de un
árbol de análisis sintáctico distinto. Si existe una cadena con más de una
derivación a la izquierda o a la derecha, también es ambigua.
Def: Un lenguaje es intrínsecamente ambiguo si no existe ninguna gramática

no ambigua que lo genere.
Ejercicio
Ver si la siguiente gramática es ambigua o no, si w = a:=b+c*a
∑ ={a, b, c, +, *, (, ), :=}
Los símbolos de este alfabeto son llamados tokens.
P
S → I:=E
I → a|b|c
E → E + E | E * E | (E) | I
V={S, I, E}
54
Hagamos derivaciones más a la izquierda para obtener la cadena w

m.i . m.i . m.i . m.i . m.i . *
S ⇒ I:=E ⇒ a:=E ⇒ a:=E+E ⇒ a:=b+E ⇒ a:=b+E*E ⇒ a:=b+c*a
Hagamos ahora otras derivaciones,

*
S ⇒ I:=E ⇒ a:=E ⇒ a:=E*E ⇒ a:=E+E*E ⇒ a:=I+E*E ⇒ a:=b+c*a
Hemos encontrado dos distintas derivaciones, con lo cual queda demostrado que dicha
gramática es ambigua.
Simplificación de gramáticas.
Ejemplos de gramáticas mal escritas
S→A
A→B
B→C ≡ S → a|S
C→D
D → a|A
Eliminación de símbolos inútiles

Este algoritmo se divide en dos etapas, que hay que aplicar en ese orden.
Ej
S → Aa | B | D
B→b
A → aA | bA | B
C → abd
1ª etapa
Creamos un nuevo conjunto llamado V', que en principio es vací
o.
V '={ ∅ }
Como primer paso, metemos en el conjunto todos aquellos no terminales que producen
SÓLO terminales, en alguna de sus producciones. Vemos que es el caso de de B y C,
luego,
V '={B, C}
Como segundo paso, metemos todos aquellos no terminales que en alguna de sus
producciones tengan algún terminal. Es el caso de S (S → aA) y A (A → aA | bA).
V '={B, C, S, A}
Como último paso, hay que eliminar todas aquellas producciones que no estén en el
conjunto V ', vemos que en este caso únicamente es D, que está en la producción S. Esto
ocurre ya que desde S se puede llegar a D, pero la producción D no está, luego sobra.
De momento la gramática nos queda:
55
S → Aa | B
B→b
A → aA | bA | B
C → abd
2ª etapa
Definimos un conjunto J que será el de variables a analizar. Inicialmente contiene el
símbolo S. Definimos el conjunto V '', que también contiene inicialmente el símbolo S.
Y sea T 'el conjunto de símbolos terminales.
J= V ''={S}
T '={ ∅ }
Paso 1:
Sacamos un no terminal de J, en este caso únicamente podemos sacar S.
Luego vamos a analizar S, S → Aa | B.
Para cada producción de S, añadimos a V ''todos los no terminales de dicha producción,
y también añadimos a J dichos no terminales, ya que los analizaremos. En este caso:
V ''={S, A, B}, J={A, B}
También añadimos a T 'los terminales que haya en dicha producción, en este caso:
T '={a}
Paso 2:
Repetir paso 1. Sacamos de J un no terminal, A por ejemplo. A → aA | bA | B
Vemos que todos los no terminales de A, ya están en V '', luego no hacemos cambios. Y
también están o estuvieron en J, pero vemos que para el conjunto T ', aparece el
terminal "b", que no estaba. Lo añadimos.
V ''={S, A, B}; J={B}; T '={a, b}
Paso 3:
Sacamos de J otro no terminal, el único que nos queda, B. B → b
Evidentemente, como no tiene producciones de no terminales, J se queda vacío, y V ''
no sufre cambios. Y tampoco T ', ya que la "b" ya estaba.
En este momento, como tenemos J={ ∅ }, paramos. Hemos de eliminar todas

las variables que no estén en V ''y todos los terminales que no estén en T ', y
aquellas producciones que contengan alguna variable que no esté en V ''o T '.
En esta caso, Como la C no está en V '', la eliminamos. Y como la "d" no está en T ',
eliminamos dicha producción. La gramática queda:
S → Aa | B
B→b
A → aA | bA | B
Otro ejemplo
S → AB|a
A→a
56
1ª etapa
V '={ ∅ }
Metemos las variables que generen algún terminal.
V '={S, A}
Vemos que B no está, eliminamos toda la producción donde se encuentra esa variable.
La gramática queda:
S→a
A→a
2ª etapa
J= V ''={S}
T '={ ∅ }
Paso 1:
Analizando S. S → a
J={ ∅ }
V ''={S}
T '={a}
Como J={ ∅ }, paramos. Vemos que A∉ V '', eliminamos la producción.

La gramática queda:
S→a
Eliminación de producciones vacías.

Antes de empezar a explicar este algoritmo, definamos dos términos.
Def: Se llama producción nula a aquella producción del tipo A → .
*
Def: Un símbolo no terminal es anulable si A ⇒
Ejemplo del algoritmo

S → aA
A → aA |
Sea H el conjunto de símbolos anulables. Siguiendo las definiciones anteriores, A es

anulable, ya que A → . Luego H={A}

Luego para cada elemento de H, deberemos quitar ε , esto se hace del siguiente modo:
S → aA (se queda igual)

A → aA|a
Otro ejemplo
S → Abb | ABC
A → aA |
B → bB |
C → abC | AB
El conjunto de símbolos anulables en este caso es:
57
H={A, B, C, S}
Nota: Si S es anulable, ∈L(G)

Luego, la gramática nos queda:
S → ABb | Ab | Bb | b
S → ABC | AB | AC | BC | A | B | C
A → aA | a
B → bB | b
C → abC | ab
C → AB | A | B
S→
(ya que S es anulable)
Eliminación de producciones unitarias

Una producción es unitaria si es del tipo:
A→B
B → w|c
En realidad debería ser: A → w|c. Veamos cómo eliminar eso.
Ejemplo:
S → A|Aa
A→B
B → C|b
C → D|ab
D→b
Llamaremos a H al conjunto de las parejas que están compuestas por un no terminal que
produce y otro producido, es decir, si por ejemplo A → B, en el conjunto deberíamos
añadir el par (A, B). Por esta regla, tenemos:
H={(S, A), (A, B), (B, C), (C, D)}
Ahora tenemos que tener en cuenta todos los pares de la forma (A, B) y (B, C), entonces
debemos añadir el par (A, C), y así sucesivamente. Luego,
H={(S, A), (A, B), (B, C), (C, D), (S, B), (S, C), (S, D), (A, C), (A, D), (B, D)}
Como último paso tengamos en cuenta la gramática que nos dan.

Debemos escribir una segunda gramática que tan sólo contenga aquellas producciones
donde aparecen terminales, es decir:
S → Aa
B→b
C → ab
D→b
58
Y ahora, con cada uno de los pares de H, formamos la gramática final. Lo hacemos
mirando los dos símbolos del par, es decir, si tenemos (S, B), deberemos añadir una
producción S → B, mirando antes en la anterior gramática qué es lo que produce B, y
vemos que en este caso, B → b, luego la producción sería S → b. Al final, la gramática
queda:
S → Aa | b | ab
B → b | ab
C → ab | b
D→b
A → b (no sufre modificación)
Teor: Cuando haya que limpiar una gramática, el orden a seguir será siempre
éste:
1) Eliminar producciones inútiles
2) Eliminar producciones vacías
3) Eliminar producciones unitarias
4) Eliminar producciones inútiles
Algoritmo de Eliminación de recursividad indirecta.

Ejemplo
S → Aa | b
A → Ac | Sd |
Como vemos S → A, y A → S, luego tenemos recursividad indirecta.
En este caso habría que sustituír la producción A → Sd de tal manera que se elimine la
recursividad y a la vez no se modifique el lenguaje que genera dicha gramática. En
principio dejamos la producción S igual, y convertimos la producción Sd a lo siguiente:
Si S → Aa | b,
Sd = Aad | bd (se sustituye la S por todas las producciones de S, concatenadas con la d
que ya estaba).
Luego, la gramática queda:

S → Aa | b
A → Ac | Aad | bd |
59
Equivalente a eliminación de recursividad por la derecha:
Sabiendo que:
A→ β T |β
T → α T |α
S → Aa | b
A → bdT | T | bd |

T → cT | adT | c | ad
Forma normal de Greibach.

Si todas las producciones de la gramática son del tipo
A → a α , con a∈ ∑ , A∈V, α ∈V*.
• No puede ser recursiva por la izquierda

• No puede generar lenguajes vacíos
La forma de conversión es la siguiente:

Si tenemos,
A → BB | a
B → AA | b
Se convierte en:
A1 →A 2 A 2 | a
A 2 →A1A1 | b
A1 →A 2 A 2 | a
A 2 → A 2 A 2 A 1 | aA 1 | b
A1 →A 2 A 2 | a
A 2 → aA 1 A 3 | bA 3 | aA 1 | b
A 3 → A 2 A1A 3 | A 2 A1
Ahora hay que poner A 3 en términos de A 2
A1 →A 2 A 2 | a
A 2 → aA 1 A 3 | bA 3 | aA 1 | b
A 3 → aA 1 A 3 A 1 A 3 |bA 3 A 1 A 3 |aA 1 A 1 A 3 |bA 1 A 3 |aA 1 A 3 A 1 |bA 3 A 1 |aA 1 A 1 |bA 1
Y por último, reescribir A 1 .
A 1 → a | aA 2 A 3 A 2 | bA 3 A 2 | aA 2 A 2 | bA 2
60
A 2 → aA 1 A 3 | bA 3 | aA 1 | b
A 3 → aA 1 A 3 A 1 A 3 |bA 3 A 1 A 3 |aA 1 A 1 A 3 |bA 1 A 3 |aA 1 A 3 A 1 |bA 3 A 1 |aA 1 A 1 |bA 1
Def: Una gramática es recursiva si desde un símbolo no terminal A puedo

volver a llegar a A, es decir:
*
∃ A∈V | A ⇒ αΑβ , α , β ∈ (∑ ∪V ) *
Teor: La recursividad es la que permite generar lenguajes infinitos.
Forma normal de Chomsky.

Hay que suponer que se parte con una gramática "limpia"
Ej.:
S → bA | aB
A → bAA | aS | a
B → aBB | bS | b
Se procede del siguiente modo:

S → CA | DB
A → CAA | DS | a
B → DBB | CS | b
C→b
D→a
S → CA | DB
A → CE | DS | a
B → DF | CS | b
C→b
D→a
E → AA
F → BB
Al final todas las producciones tienen que ser del tipo

A → BC ó
A→a
B, C∈V, a∈ ∑
Lema del Bombeo para CFL.

Al igual que para los lenguajes regulares, existe el lema del bombeo para los lenguajes
independientes del contexto. Análogamente al caso anterior, en este un lenguaje ha de
cumplir el lema del bombeo si es CFL, si no lo cumple, no lo es. Y también es posible
que si lo cumple sea CFL o no lo sea.
61
Sea L CFL | å∉ L
∃ k∈Ν | si z∈L, |z|>k:
1) z = uvwxy
2) |vwx| ≤ k
3) uv i wx i y∈L, ∀ i ≥ 0
4) |vx| ≥ 1 (es decir, v y x no pueden ser ε a la vez)
Dem:
L={a i b j | j = i²}
Sea k la constante del lema del bombeo.
2
Sea z = a k b k ∈L
Si |z| > k ⇒
1) z = uvwxy 3) |vx| ≥ 1
2) |vwx| ≤ k 4) uv i wx i y∈L, ∀ i ≥ 0
2
Si z = a k b k = uvwxy
Supongamos v = a r b s ⇒ v i = (a r b s ) i ⇒ uv i wx i y∉L, porque habría símbolos b
antes que a, por ejemplo:
v² = a r b s a r b s .
Lo mismo ocurre con la "x"
Casos que quedan:

a) v = a r x = a s
|vx| ≥ 1 ⇒ r + s ≥ 1 (3)
2
+r +s
z²=uv²wx²y = a k b k ∉L, ya que k² ≠ (k + r + s)²
b) v = b r x = b s
|vx| ≥ 1 ⇒ r + s ≥ 1 (3)
2
+r +s
z i = uv i wx i y = a k b k ∉L, ya que k² + r + s ≠ k²
c) v = a r x = b s
|vx| ≥ 1 ⇒ r + s ≥ 1 (3)
2 2
z i = uv i wx i y = a k −r + ri b k − s + si
= a k +(i −1) r b k + ( i −1) s
∉L, ya que (k+(i-1)r)² ≠ k²+(i-1)s
Luego, vemos que el lenguaje no cumple el lema del bombeo, con lo cual no es CFL.
62
Otro ejemplo
L={a i b i c i | i ≥ 1} = {abc, aabbcc, aaabbbccc, aaaabbbbcccc...}
Sea n la constante del lema del bombeo

Sea z=a n b n c n ∈L
|z| > n ⇒ 1) z = xyrst 3) |ys| ≥ 1

2) |yrs| ≤ n 4) xy i rs i t∈L, ∀ i ≥ 0
si z = a n b n c n = xyrst
Como ocurre en 2), |yrs| ≤ n, las cadenas |ys| no pueden contener simultáneamente
símbolos a y c, porque entre la última a y la primera c tiene que haber al menos una b.
Casos que quedan:
a) y = a p s = aq
(3) |ys| ≥ 1 ⇒ p + q ≥ 1
z² = xy²rs²t = a n + 2 p + 2 q b n c n ∉L, ya que el número de "a" es mayor que el número
de "b" o "c"
b) y = b p s = bq
Lo mismo
c) y = c p s = cq
Lo mismo
d) y = a p s = bq
z² = xy²rs²t = a n+ p b n+ q c n ∉L, salvo que p+q = 0, pero p+q ≥ 1
e)y = b p s = cq
sea z 0 = xy 0 rs 0 t = a n b n− p c n−q ∉L
Luego, no es CFL al no cumplir el lema del bombeo.
Teor: Existen algoritmos para determinar si una CFG es finita, infinita o vacía.
Teor: Una CFG es vacía si en la eliminación de símbolos inútiles resulta
eliminada S
Teor: Una CFG es finita si no tiene ciclos dirigidos
Teor: Una CFG es infinita si tiene ciclos dirigidos.
S
Ejemplos
S → AB
A → BC | a A B
B → CC | b
C→a
C
63
Vemos que no tiene ciclos dirigidos, luego es finito

Sea ahora:
S → AB S A
A → BC | a Esta gramática sin embargo
B → CC | b tiene varios ciclos dirigidos,
C → a | AB por ejemplo A-B-C-A, lo
que hará que sea infinita.
B C
Análisis sintáctico: Algoritmo CYK (Cocke-Younger-

Kasami).
Dada G ≡ (V, ∑ , S, P), y dada w ∈ ∑ *, ¿w∈L(G)? Dicho problema se conoce como
problema de decisión.
Dada una CFG G ≡ (V, ∑ , S, P) escrita en Forma Normal de Chomsky y sin

producciones vacías. Sea x ∈ ∑ *, ∀ A∈V y ∀ w subcadena de x, es posible determinar
si A puede derivar en un nº indeterminado de pasos en w.
Ejemplo del algoritmo CYK
S → AB | BC
b a a b a
A → BA | a
1 B A, C A, C B A, C
B → CC | b
2 A, S B S, C A, S
C → AB | a
3 ∅ B B
4 ∅ S, C, A
Sea por ej, w = baaba
5 S...
Para sacar la anterior tabla se siguen los siguientes pasos:

Se construye dicha tabla poniendo en la primera fila un símbolo de la cadena por cada
celda (en este caso baaba).
En la fila número 1, tenemos que mirar el símbolo que tenemos encima. En la casilla (1,
1) es la "b". Entonces miramos la gramática, y buscamos todas aquellas variables que
produzcan directamente la "b". Vemos que en este caso, únicamente es B → CC | b,
luego en la casilla (1, 1) va una B. Lo mismo con los elementos de la fila 1, en caso de
la "a", las gramáticas que generan directamente este símbolo terminal son A y C.
Para formar la fila 2, debemos mirar los resultados obtenidos en el anterior paso, es
decir, la fila que tenemos encima. Si queremos formar por ejemplo la casilla (2, 1),
hemos de mirar la casilla justo encima de ella, es decir, la (1, 1), y la que está
inmediatamente a su derecha, es decir, la (1, 2). Vemos que tenemos en una casilla B, y
en otra A, C. Entonces entre las dos casillas formamos las combinaciones posibles, es
decir, en este caso tenemos BA y BC. Una vez tenidas las combinaciones, miramos la
gramática y vemos si existe alguna producción que las genere. Vemos que: S → AB|BC,
y A → BA | a, con lo cual vemos que S, y A generan esas dos combinaciones. Luego en
la casilla (2, 1), irá una S y una A. Las demás casillas de esa fila se forman exactamente
64
igual, mirando primero la casilla de arriba, la inmediatamente a su derecha, formando

combinaciones y mirando la gramática.
A partir de ahí, la cosa cambia. Las demás filas se deben hallar del siguiente modo:
Supondremos que tenemos dos punteros. Uno se coloca en la primera casilla de la
columna cuyo hueco queremos hallar. Por ejemplo, si fuera la casilla (3, 1),
colocaríamos el puntero en la posición (1, 1). El segundo puntero lo colocamos
exactamente en la casilla de encima de la celda que queremos hallar, pero una columna
desplazada a la derecha. Tenemos ya las dos primeras celdas de las que tenemos que
hacer las combinaciones mencionadas antes, y evidentemente miramos la gramática y
apuntamos en la celda aquellas producciones que las generen. Ahora movemos el
primer puntero en dirección vertical descendente una posición, mientras que el otro se
moverá en sentido diagonal hacia arriba-derecha una casilla. Ya tenemos otras dos
casillas de las que hacer combinaciones. Seguimos moviendo del mismo modo hasta
que el segundo puntero llegue hasta una casilla de la primera fila y el primero llegue a
una posición por encima de la casilla que estamos hallando.
Supongamos que queremos hallar la casilla marcada con "x". El sentido de los punteros
entonces es el siguiente:
b a a b a
1
2
3
4 x
5
w∈L(G) ⇔ En la última casilla de la primera fila aparece el símbolo inicial, S.

En este momento podemos parar de calcular más combinaciones, ya que la cadena será
aceptada. Si S no aparece en dicha casilla, la cadena no es generada por la gramática. En
este caso, w∈L(G).
Supongamos que tenemos la misma gramática que antes, pero la cadena es ahora
w = bbab
S → AB | BC
b b a b
A → BA | a
1 B B A, C B
B → CC | b
2 ∅ A, S S, C
C → AB | a
3 A S, C
4 S, C
w = bbab
Vemos que S está en la última casilla de la primera columna, luego w∈L(G) también.
Teor: Si L 1 y L 2 son CFL, L 1 ∪ L 2 es CFL.
Teor: Si L 1 y L 2 son CFL, L 1 · L 2 es CFL.
Teor: Si L es CFL, L* es CFL.
65
Teor: Los CFL no son cerrados respecto a la intersección, ni a la

complementación.
Autómatas a Pila No Deterministas (APND).

Son un nuevo tipo de autómata que evidentemente funciona una pila. Un APND se
define del siguiente modo:
M ≡ (∑, Q, δ , q 0 , F , Γ, Z )
Γ es el denominado Alfabeto de Pila (es decir, los símbolos que se pueden usar en la
pila).
Z es el símbolo inicial de la pila. Cuando empecemos a hacer operaciones con la pila

será el único símbolo que se encontrara en ella. Z∈ Γ .
Los demás elementos los conocemos ( ∑ , Q, F, q 0 , δ ).
Esta vez la función δ viene definida del siguiente modo:
δ : Q× ( ∑ ∪ ε ) × Γ  →℘(Q × Γ*)
(p, a, b) α {(q, w)}
p, q∈Q, a∈( ∑ ∪{ε } ), b∈ Γ , w∈ Γ *
Puede ocurrir:
· δ (p, a, b)={(q, )} (el autómata quita el símbolo b y no inserta nada
También se llama desapilar)
· δ (q, , a)={((p|q), aa)} (el autómata apila el símbolo a)

· δ (q, , a)={(q, a)}

(el autómata no modifica la pila, se queda igual)
· δ (q, a, b)={ ∅ } (el autómata no puede transitar, se detiene la ejecución)
Ejemplo
Sea M un autómata definido así:
Q={q 0 ,q 1 ,q 2 ,q 3 } F={q 3 } ∑ ={a, b} Γ ={Z, A} q0 = q0
Q /δ (a, Z) (b, Z) ( , Z)
(a, A) (b, A) ( , A)

q0 {q 1 , AZ)(q 3 , )}
{(q 3 , )}

q1 {(q 1 ,AA)} {(q 2 , )}

q2 {(q 3 , )}
{(q 2 , )}

q3
L={a i b i | i ≥ 0} ∪ {a}
66
Descripción instantánea de un autómata a pila.

Se define una descripción instantánea del siguiente modo:
D.I.= (p, u, w) ∈Q × ∑ * × Γ *
p es el estado actual
u es la cadena que queda por leer
w es el contenido de la pila (se lee en este sentido: )
(p, ax, b α ) |- (q, x, βα ) ⇔ (q, β )∈ δ (p, a, b)
p, q ∈ Q
a∈ ∑ Símbolo para representar una transición
x∈ ∑ *
b∈ Γ
α, β ∈ Γ *
*
Nota: | − significa que en cierto número de pasos llega a otra D.I.
Sea M ≡ (∑, Q, δ , q 0 , F , Γ, Z )
*
· L(M)={w∈ ∑ * | (q 0 , w, z) | − (p, ε , α ) para algún p∈F, α ∈ Γ *}
Se define otro lenguaje,

*
· N(M)={w∈ ∑ * | (q 0 , w, z) | − (r, , ) para algún r∈Q}

Éste último se denomina Lenguaje reconocido por pila vacía.
Teor: L(M) ≠ N(M) en general, aunque ambos criterios de aceptación son

equivalentes.
Teor: Un autómata a pila es determinista si en una D. I. El autómata sólo tiene

una forma de evolucionar. Si no cumple esta regla, es no determinista.
P.ej:
* ( p , u , wα )
(q, au, x α ) | − 
(r , au , γα )
Notación: Los APND también se denotan por PDA
Teor: La condición para ser determinista es:

a) card( δ (q, a, x)) ≤ 1 ∧ card( δ (q, , x))=0

ó b) card( δ (q, a, x))=0, ∀a ∈ A ∧ card( δ (q, , x)) ≤ 1

Teor: Si un DFA/NFA reconoce un lenguaje, un PDA también puede.
67
P.ej.:
NFA ≡ ( ∑ , Q, F, q 0 , δ )
PDA ≡ (∑, Q, δ , q 0 , F , Γ, Z ) .
En este caso no se usarán Γ ni Z, para que el comportamiento del PDA

sea igual al del NFA
a
a
A B
Q={A, B}
∑ ={a} Q/ δ (a, Z)
q 0 =A A {(B, Z)}
F={B} B {(B, Z)}
Teor: El conjunto de los lenguajes que reconocen los autómatas a pila es al

menos el de los lenguajes regulares
Sea
, Q, δ , q 0 , F , Γ, Z ) tal que L(M) = L(G)
G ≡ (V, ∑ , S, P), y M ≡ (∑'
Q={A, B, C}
F={C}
q 0 =A
∑ = ∑'
Γ ={Z} ∪ V ∪ ∑
Z=Z
δ (A, , Z) = {(B, SZ)}

δ (A, , R) = {(B, w) | (R → w) ∈P}, ∀ R∈V

δ (A, a, a) = {(B, , }}, ∀ a∈ ∑

δ (B, , Z) = {(C, )}

L(M) = L(G)
Ejemplo:
Buscar un autómata tal que:
L={w∈{a, b}* | n a (w)=n b (w)} (el número de "a" sea igual al de "b")
Q/ δ ( ,Z)

(a,Z) (b,Z) (a,A) (b,A) (
,A) (a,B) (b,B) (
,B)
Q={q 0 , q 1 }, F={q 1 } q0 {(q 1 , )} {(q 0 ,AZ)} {(q 0 ,BZ)} {(q 0 ,AA)} {(q 0 ,

)} {∅} {(q 0 ,
)} {(q 0 ,BB)} {∅ }
Γ ={Z, A, B} q1
68
Ejemplo:
S → aSa | bSb |
L(G)={w· w i | w∈{a, b}*}
Si quisiéramos hacer el PDA, la función δ se define de este modo:
δ (q 0 , )={(q 1 , SZ)}

δ (q 1 , a, a)= δ (q 1 , b, b)={(q 1 , )}

δ (q 1 , , S)={(q 1 , aSa), (q 1 , bSb), (q 1 , )}

δ (q 1 , , Z)={(q 2 , )}

Sea por ejemplo w = abba

(q 0 , abba, z) |- (q 1 , abba, SZ) |- (q 1 , abba, aSaZ) |- (q 1 , bba, SaZ) |-
*
(q 1 , bba, bSbaZ) |- (q 1 , ba, SbaZ) |- (q 1 , ba, baZ) | − (q 1 , , Z) |- (q 2 , , )

Teor: Dado un PDA M ≡ (∑, Q, δ , q 0 , F , Γ, Z ) , ∃M '≡ (∑' , δ 'q 0', F '

, Q' , Γ'
, Z ')
tal que N(M')=L(M)
Q '= Q ∪ {q 0', q5 }
q '0=q 0
Γ'= Γ ∪ {Z '
}
δ '= δ
Z '=Z
F '={ ∅ }
a) δ '(q '0, ε , Z ') = {(q 0 , ZZ ')}

b) δ '(q, ε , A) = {( q5 , A)}, ∀q ∈ F , ∀A ∈ Γ ∪ {Z '
}
c) δ '(q 5 , ε , A) = {( q5 , ε )}, ∀A ∈ Γ ∪ {Z '
}
Nota: M nunca quitaría Z' de la pila y por lo tanto no podría aceptar por
pila vacía.
Teor: La pila de un PDA no es finita.
Teor: Dado un PDA M ≡ (∑, Q, δ , q 0 , F , Γ, Z ) , ∃M '≡ ( ∑' , δ 'q 0', F '

, Q' , Γ'
, Z ') |
L(M') = N(M)
Q'= Q ∪ {q 0', q f } Γ'= Γ ∪ {Z '

}
'
q =q 0
0 Z '=Z
δ '= δ F '={ q f }
69
a) δ '(q '0, ε , Z ') = {(q 0 , ZZ ')}

b) δ '(q i', ε , Z ') = {( q f , ε )}, ∀qi ∈ Q
Teor: Dado un PDA M ≡ (∑, Q, δ , q 0 , F , Γ, Z ) , ∃ G ≡ (V, ∑ , S, P) | L(G)=N(M)

V: donde p, q∈Q y A ∈ Γ .
El objetivo del autómata es ir de p a q eliminando A de la pila.
Tipos de producciones:
a) (S → <q 0 Z p>)∈P, ∀p ∈ Q
b) Si (p, ε ) ∈ δ (q, a, A) ⇒ (<q A p> → a) ∈P
c) Si (p 0 , α ) ∈ δ (q, a, A), α = B1 B2 ...Bm ,
===, ∀pi ∈ Q
Las producciones son:

(<q A p m > → a ... )∈P, ∀p i ∈ Q
Ejemplo:
Sea el PDA, Q={q 1 , q 2 , q 3 }, F={q 3 }, q 0 =q 1 , Γ ={A, Z}, ∑ ={a, b}
δ (q 1 ,a, Z)={(q 1 , AZ)}

δ (q 1 ,a, A)={(q 1 , AA)}
δ (q 1 ,b, A)={(q 2 , )}
δ (q 2 ,b, A)={(q 2 , )}
δ (q 2 , , A)={(q 2 , )}

δ (q 2 , , Z)={(q 3 , )}

→ S → <q 1 Z q 1 > | <q 1 Z q 2 > | <q 1 Z q 3 >

Aplicando a) 
Aplicando b) 
→ 3) <q 1 A q 2 > → b
4) <q 2 A q 2 > → b
5) <q 2 A q 2 > →
6) <q 2 Z q 3 > →
Aplicando c) 
→ 1) <q 1 Z q 1 > → a <q 1 A q 1 ><q 1 Z q 1 > | a<q 1 A q 2 ><q 2 Z q 1 >
| a<q 1 A q 3 ><q 3 Z q 1 >
<q 1 Z q 2 > → a<q 1 A q 1 ><q 1 Z q 2 > | a<q 1 A q 2 ><q 2 Z q 2 >

| a <q 1 A q 3 ><q 3 Z q 2 >
<q 1 Z q 3 > → a<q 1 A q 1 ><q 1 Z q 3 > | a<q 1 A q 2 ><q 2 Z q 3 >

| a<q 1 A q 3 ><q 3 Z q 3 >
70
2) <q 1 A q 1 > → a<q 1 A q 1 ><q 1 A q 1 > | a<q 1 A q 2 ><q 2 A q 1 >

| a<q 1 A q 3 ><q 3 A q 1 >
<q 1 A q 2 > → a<q 1 A q 1 ><q 1 A q 2 > | a<q 1 A q 2 ><q 2 A q 2 >

| <q 1 A q 3 ><q 3 A q 2 >
<q 1 A q 3 > → a<q 1 A q 1 ><q 1 A q 3 > | a<q 1 A q 2 ><q 2 A q 3 >

| a<q 1 A q 3 ><q 3 A q 3 >
Otro ejercicio
Sea el PDA: Q ={q 1 , q 2 }, Γ ={A, Z}, ∑ ={a, b}, F={q 2 }
Hallar la gramática.
1) δ (q 1 , a, Z) = {(q 1 , AZ)}
2) δ (q 1 , b, A) = {(q 1 , AA)}
3) δ (q 1 , a, A) = {(q 2 , )}

0) S → <q 1 Z q 1 > | <q 1 Z q 2 >

3) <q 1 A q 2 > → a
1) <q 1 Z q 1 > → a<q 1 A q 1 > <q 1 Z q 1 > | a<q 1 A q 2 ><q 2 Z q 1 >
<q 1 Z q 2 > → a<q 1 A q 1 > <q 1 Z q 2 > | a<q 1 A q 2 ><q 2 Z q 2 >
2) <q 1 A q 1 > → b<q 1 A q 1 > <q 1 A q 1 > | b<q 1 A q 2 ><q 2 A q 1 >
<q 1 A q 2 > → b<q 1 A q 1 > <q 1 A q 2 > | b<q 1 A q 2 ><q 2 A q 2 >
Teor: L ⊆ ∑ * ⇔ ∃ PDA M ≡ (∑, Q, δ , q 0 , F , Γ, Z ) | L=L(M)
71
Tema 5
Máquinas de Turing.
Una máquina de Turing se caracteriza porque tiene memoria infinita. La
máquina puede escribir en la cinta, y luego moverse.
Dibujo ilustrativo
q0
q5 q1
q4 q2
q3
Una Máquina de Turing se define del siguiente modo:

TM ≡ (Q, ∑, δ , q 0 , F , Γ, )
Γ será en este caso el alfabeto de cinta, y es un símbolo nuevo llamado "blanco".

∈Γ, ∉∑.
∑ es la entrada, y como ya dijimos, Γ será la cinta.
La función δ viene definida así:
δ : Q× Γ  → Q × Γ × {L, R}
(q, a) α (p, b, x)
p, q∈Q
a, b∈ Γ
x∈{L, R}
{L, R} es el conjunto que define el movimiento del autómata por la cinta. L indica que
después de realizar la operación, dicha máquina se mueve hacia la izquierda (Left), y R,
que se mueve a la derecha (Right). Hay también otra opción que es S, y significa
quedarse parado (Stop), que equivale a moverse primero a la izquierda y luego a la
derecha, o primero a la derecha y luego a la izquierda.
L = {a n b n c n | n ≥ 0} es Turing-Computable.
72
Ejemplo
a b c d
q5
δ (q 5 , b) = (q 90 , o, R)
a o c d
q 90
Ejemplo
Q={q 1 , q 2 }, F={q 2 }, ∑ ={a, b}, Γ ={a, b, }, q 0 =q 1 .

δ (q 1 , a)=(q 1 , a, R)
δ (q 1 , b)=(q 1 , a, R)
δ (q 1 , )=(q 2 , , L)
Sea por ejemplo la cadena w = aabb
a a b b a a b b
q1 q1
a a a b a a a a
q1 q1
Teor: Si δ (q, a) no está definida, la máquina se dice que está parada.
Descripción instantánea de una Máquina de Turing.

Para hacer las descripciones instantáneas en una TM, hay dos formas:
a) (q i , w 1 aw 2 ), q i ∈Q, w 1 , w 2 ∈ Γ *, a∈ Γ
b) a 1 a 2 ...a k q i a k +1 a k + 2 a n ≡ (q i , a 1 a 2 ...a k a k +1 a k + 2 a n )
73
En la TM de antes hagamos la descripción instantánea:
(q 1 , aabb) |- (q 1 , aabb) |- (q 1 , aabb) |- (q 1 , aaab) |- (q 1 , aaaa ) |- (q 2 , aaaa)
Usando la forma b)
q 1 aabb |- aq 1 abb |- aaq 1 bb |- aaaq 1 b |- aaaaq 1 |- aaaq 2 a
Ejemplo
Q={q 1 ,q 2 ,q 3 }, F={q 3 }, ∑ ={a, b}, Γ ={a, b, }, q 0 = q 1

δ (q 1 , a) = (q 1 , a, L)
δ (q 1 , b) = (q 1 , b, L)
δ (q 1 , ) = (q 2 , ,R)
δ (q 2 , a) = (q 3 , a, L)
δ (q 2 , b) = (q 3 , b, L)
δ (q 2 , ) = (q 3 , , L)
(q 1 , aababb) |- (q 1 , aababb) |- (q 1 , aababb) |- (q 1 , aababb) |- (q 1 , aababb)

|- (q 2 , aababb) |- (q 3 , aababb)
A partir de ahora, los q∈F no tendrán transiciones (por convenio).
Def: Se denomina computación de una TM a la secuencia de movimientos

que conduce a la máquina a una parada.
Def: Sea TM ≡ (Q, ∑, δ , q 0 , F , Γ, ), se define el lenguaje aceptado por una TM:

*
L(M)={w ∈ ∑ * | (q 0 , w) | − (p, w 1 aw 2 ), para algún p∈F}
La máquina tiene que estar parada, pero se asume que no hay
transiciones para p.
Ejemplo
L(M)=L(a*)
Q = {q 0 , q 1 }, Γ ={a, b, }, q 0 =q 0 , F = {q 1 }, ∑ ={a}
δ (q 0 , a)=(q 0 , a, R)
δ (q 0 , )=(q 1 , , L)
Veamos ahora otro ejemplo para el mismo lenguaje pero con una TM distinta.
Q = {q 1 , q 2 ,q 3 }, Γ = {a, b, }, q 0 =q 1 , F = {q 3 }, ∑ ={a, b}
74
δ (q 1 , a)=(q 1 , a, R)
δ (q 1 , b)=(q 2 , b, R)
δ (q 1 , )=(q 3 , , S)
δ (q 2 , a)=(q 2 , a, R) Este es un bloque de transiciones definido de tal manera que

δ (q 2 , b)=(q 2 , b, R) si entra en el estado q 2 , la máquina nunca se parará. Es otro
modo de decir que la máquina rechaza la cadena. Como
δ (q 2 , )=(q 2 , , R) vemos esto ocurre por ejemplo cuando llega una "b".
Entonces hemos visto dos formas de que la máquina rechace
las w∉L(M), en estos dos últimos ejemplos.
Ejercicio
Hacer una TM que reconozca el siguiente lenguaje.
L={a n b n | n ≥ 1}
Q={q 0 ,q 1 ,q 2 ,q 3 ,q 4 }, F={q 4 }, Γ ={a, b, , c, d}, q 0 =q 0
δ (q 0 , a)=(q 1 , c, R) Cambia "a" por "c" y busca a la

δ (q 1 , a)=(q 1 , a, R) derecha la primera "d"
δ (q 1 , b)=(q 1 , d, L)
δ (q 1 , d)=(q 2 , d, L)
δ (q 2 , d)=(q 2 , d, L) Se mueve a la izquierda buscando

δ (q 2 , a)=(q 2 , a, L) la primera "c"
δ (q 2 , c)=(q 0 , c, R)
δ (q 0 , d)=(q 3 , d, R) Si estamos aquí, es porque se marcó la última "a"
δ (q 3 , d)=(q 3 , d, R)
δ (q 3 , )=(q 4 , , S} Aceptará si estando en q 3 lee un blanco en la cinta,
porque habrá igual número de "c" que de "d"
75
Diagramas de transición para una Máquina de Turing.

También existen los diagramas de transición para TM. Supongamos que tenemos como
ejemplo la siguiente función δ :
δ 0 1
q0 ---------------- (q 1 , 0, R)
q1 (q 2 , 1, R) (q 1 , 1, R)
q2 (q 3 , 0, L) ----------------
q3 (q 0 , 0, R) (q 3 , 1, L)
Si quisiéramos dibujar el diagrama de transiciones, sería del siguiente modo:
1/1
q0
1/0
L R q1
0/0 0/1
0/0
q3 L R q2
1/1
Como vemos, cada transición tiene asociada un i/j. La i corresponde al símbolo que lee
en la cinta actualmente, y la j al símbolo con el que reemplazará antes de moverse dicho
símbolo i. Por ejemplo, 0/1 implica que leyendo un 0 en la cinta, lo sustituirá por un 1.
Simplificaremos aún más el diagrama anterior, cuando tengamos transiciones del tipo
0/0, escribiremos simplemente un 0, e igualmente con 1/1, escribiremos un 1. Es decir:
a/a ⇒ a, ∀ a ∈ Γ
Por otro lado, si tenemos una transición i/j, donde i = j, hacia un mismo estado, esa
transición se puede obviar y no dibujarla, ya que en realidad nos estamos quedando en
el mismo estado.
Por último resaltar que aquellas transiciones que no estén definidas, como por ejemplo
en este caso, δ (q 0 , 0), se debe dibujar una transición saliente del estado, pero que no
incide en ningún otro estado, sino se queda "en el aire". Entonces, el anterior diagrama
nos quedaría del siguiente modo
76
0
1/0
R R
0 0/1
0 1
L R
Nota: Si hubiera algún estado de aceptación se representaría igual que en los

demás autómatas.
0
q3 L R q2
1/1
Ejercicio
Hacer el diagrama de transiciones para el autómata L={a n b n | n ≥ 1}
bcb cb
a/c
R R
d c b/d
abc R L
bb
abcdb
L
77
Teor: Los lenguajes reconocidos por una TM son los lenguajes

recursivamente enumerables. La TM procesa, para y acepta. La
máquina también puede no parar. Evidentemente, si no para, la cadena
ante la que no paró no pertenece al lenguaje.
Def: Se llaman lenguajes recursivos a aquellos donde existe al menos una

TM que se pare ante cualquier cadena, es decir, no puede quedarse
"colgada" (no parar).
Teor: Lenguajes Recursivos ⊂ Lenguajes Recursivamente Enumerables.
Def: Definición de Función Turing-Computable

f: ∑ * → ∑ * es Turing-Computable sii ∃ TM
M ≡ (Q, ∑, δ , q 0 , F , Γ, → pu, para algún p ∈ F, cuando f(w)=u
) | q0w 
Teor: Las TM pueden hacer cualquier operación (sumar, restar...)
Ejemplo de suma
F(m, n)=n + m
q/a a
q1 (q 1 , a, R) ----------------
q2 (q 2 ,a, R) (q 3 , ,L)
q3 (q 4 , b, L) ----------------
q4 (q 4 , a, L) (q 5 , , R)
b/a b a/b b
R R L L R
b b b,b b b , b, a
Combinación de Máquinas de Turing.

Es posible combinar varias máquinas de Turing y así su funcionamiento.
M 1 ≡ (∑, Q1 , q 01 , δ 1 , Γ, F1 , )
M 2 ≡ (∑, Q2 , q 02 , δ 2 , Γ, F2 , )
Se supone que Q 1 ∩ Q 2 = ∅ .
La máquina M 1 combinada con M 2 sería:
78
M 1 · M 2 ≡ (Q, ∑, δ , q 0 , F , Γ, )
Q= Q 1 ∪ Q 2
q 0 =q 01
F=F 2
δ ( q, a )
· δ 1 (q, a), si q∈Q 1 y δ 1 (q, a) ≠ (p, b, x), ∀p ∈ F1
· (q 02 , b, x) si q∈Q 1 y δ 1 (q, a)=(p, b, x), ∀p ∈ F
· δ 2 (q, a) si q∈Q 2
Otros tipos de Máquinas de Turing.

M. T. con múltiples pistas → δ :Q× Γ k 
→ Q× Γ k × {L, R, S}
M. T. con cinta infinita en un único sentido →
M. T. Multicinta → δ :Q× Γ n 
→ Q× Γ n × {L, R, S} n
Tiene n cintas con las que se puede operar simultáneamente.
M. T. con cinta multidimensional → Permiten movimientos en diagonal.

δ : Q× Γ → Q × Γ × {L, R, U , D, S }
M. T. no determinista → δ : Q × Γ 
→ ℘ (Q × Γ × {L, R} )
M. T. universal (Mu)
Toma como entrada una cadena y una codificación de una T. M. y simula el
comportamiento de la T. M. ante la entrada. Mu(M, w)
Mecanismo para codificar la Máquina de Turing

Universal.
Q={q 1 , ... , q n }, q 0 =q 1 , F={q n }, Γ ={a 1 , ..., a n }, ∑ ={0, 1}
Viendo el alfabeto, sabemos que vamos a tener que codificar en unario.
Por ejemplo, q 3 =111

q 5 =11111
q 1 =1
Del conjunto {L, R}, codificaremos L = 1 y R = 11
79
Entonces, si tenemos por ejemplo:

δ (q 3 , a 2 ) = (q 5 , a 1 , R)
La codificación sería: 011101101111101011
q 3 a 2 q 5 a1 R
δ (q 1 , a 1 ) = (q 1 , a 1 , R) → 010101010110
δ (q 1 , a 2 ) = (q 3 , a 1 , L) → 01011011101010
Teor: Sea el DFA M ≡ ( ∑ , Q, F, q 0 , δ ), ∃ TM M '≡ (Q ' ,δ '

, ∑' , Γ,
, q 0', F ' )|
L(M)=L( M ')
Q '= Q ∪ {q f } , F '= {q f } , ∑'= ∑ , q 0' = q 0
δ '(q, a)=( δ (q, a), a, R), ∀ q∈Q, ∀ a∈ ∑

δ '(q, )=(q f , , S), ∀ q∈F
Teor: Si L es regular, entonces L es recursivamente enumerable.
Teor: Si L es regular, entonces L es recursivo.
Teor: Una TM se comporta un PDA simulando la pila con otra cinta.
Teor: Si L es CFL, entonces L es recursivo
Teor: Si L 1 y L 2 son recursivos, L 1 ∩ L 2 es recursivo
Sean M 1 y M 2 las TM que reconocen L 1 y L 2 respectivamente.

Si w∈L i ⇒ M i para y acepta w
Si w∉L i ⇒ M i para y rechaza w
w no
M no
?
sí
no
no
sí
M sí
w∈L(M) ⇔ w∈L(M 1 ) ∧ w∈L(M 2 ) ⇔ w∈ L(M 1 ) ∩ L(M 2 )= L 1 ∩ L 2
80
Teor: Si L es recursivo sobre ∑ , ∃ TM M | L=L(M). M para ante cualquier

__
cadena. En este caso, L también para siempre.
__
Teor: Si L es recursivo, entonces L es recursivo, es decir, para siempre. Esto
no ocurre en los recursivamente enumerables.
__
Teor: ∃ L. R. E. | L no es L. R. E.
Teor: Si dos lenguajes son recursivos, la unión también lo es.
Teor: Si dos lenguajes son recursivamente enumerables, la unión también lo

es.
__
Teor: Si un lenguaje L y su complementario L son recursivamente
__
enumerables, entonces L y L son recursivos.
__
Dados L, L ⊆ ∑ *
__
a) L y L son recursivos
__
b) Ni L ni L son recursivamente enumerables.
c) Uno de los dos es recursivamente enumerable pero no recursivo y el otro no
es recursivamente enumerable.
Procedimiento efectivo (o algoritmo) M.

1) Está especificado por un número finito de instrucciones (cada instrucción
especificada con un número finito de símbolos)
2) M produce un resultado deseado en un número finito de pasos si se ejecuta

sin error
3) M puede ser realizada por un humano usando lápiz y papel sin ayuda
externa.
4) No se requiere del humano, ni trucos, ni ingenuidad. A las funciones que

ejecutan estos procedimientos se les llama efectivas.
Tesis de Church-Turing: La clase de las funciones efectivamente computables

son las funciones Turing-computables.
Teor: Un L es recursivamente enumerable sii L = L(G), para alguna gramática

G no restringida (de tipo 0)
81
Recursivamente Enumerables
Recursivos
Dependientes del contexto
Independientes del Contexto
Regulares
82
Tema 6
Resolubilidad.
Dado ∑ , sea L ⊆ ∑ *
Def: Se denomina Χ L a la función característica del lenguaje. Se define:

ΧL : ∑* → {0, 1}
Χ L (w)=0 si w∉L, 1 si w∈L
Teor: Χ L es computable (Turing-computable) si L es recursivo.
Teor: Χ L no es computable si L es recursivamente enumerable.
Problemas
π AMB Dada una CFG G, ¿es G ambigua? (sin solución)

π DFA Dado un DFA M y w∈ ∑ * , ¿M acepta w?
*
π CFG Dada una CFG G y w∈ ∑ * , ¿S ⇒ w?
π CFG−VAC Dada una CFG G, ¿es L(G)= ∅ ?
π HP Dada una TM M, w∈ ∑ * , ¿M para ante w?
Problemas de decisión (sin solución).
π FIND Dada una CFG G, hallar w∈ ∑ * | w tiene 2 o más árboles de derivación.
Este último problema sin embargo no es de decisión.
Supongamos que π AMB tiene solución.
Sí
π AMB (G)
No ⇒ π FIND = No
Supongamos que pudiéramos contestar a π FIND .
No ⇒ π AMB = No
π FIND
Sí (w) ⇒ π AMB = Sí
83
Teor: A partir de un problema de decisión se pueden resolver problemas que

no son de decisión.
π DFA (M, w)
Instancia ( π HP (M, w))
π AMB (G)
Dado π , D π ={ instancias de π }
D π =S π ∪ N π
Donde S π ={ instancias de π con respuesta afirmativa }

N π ={ instancias de π con respuesta negativa }
Sπ ∩ Nπ =∅
π es resoluble sii ∃ TM M ≡ (Q, ∑, δ , q 0 , F , Γ, ), que para ante cualquier entrada

w ∈ ∑ * , y que ante C(I) (siendo C(I) una codificación de ∑ en I∈ D π determina si la
instancia pertenece o no a S π , I∈S π
π es resoluble sii existe un algoritmo que es capaz de responder sí o no a cada una de

las I ∈ Dπ
π es resoluble sii el lenguaje que codifica S π es recursivo
π es irresoluble si se niega alguna de las anteriores.
Def: Dado π y π ', se dice que π se reduce a π 'si un algoritmo que resuelva
π 'pueda usarse para resolver π .
Teor: Si π se reduce a π ', y π 'es resoluble, entonces π es resoluble
Teor: Si π se reduce a π ', y π 'es irresoluble, entonces π es irresoluble
Problema de la parada
π HP
Dada TM M arbitraria con alfabeto ∑ y w ∈ ∑ * , ¿Para M ante w?
Dem: Demostración de que π HP es irresoluble.
∑ * ={w 1 , w 2 ,w 3 ..............}
TM( ∑ )={M 1 , M 2 , M 3 ...........}
84
L={w i | w i no es aceptada por M i }

Lema: L no es recursivamente enumerable.
Supongamos que L es recursivamente enumerable ⇒ L=L(M k )
Consideremos w k , si w k ∈L(M k ) ⇒ w no es aceptada por M k ⇒ w∉L(M k )

Lo que es absurdo.
Conclusión: L no es recursivamente enumerable.
Supongamos M HP (M, w) 
→ sí o no.
Construyamos M L | L=M L (si se consigue construir, es que algo va mal...)
Sea w∈ ∑ * ,
1) M L enumera ∑ * : w 1 , w 2 , ... Hasta hallar w k =w

2) M L genera M k
3) M L pasa (M k , w k ) a la M HP
Para ⇒ Paso 4)
M HP (M k , w k )
No para ⇒ M L para y dice que acepta w = w k
4) M L pasa (M k , w k ) a Mu (M.T. Universal).
Acepta ⇒ M L para y rechaza w k

Mu(M k , w k )
Rechaza ⇒ M L para y acepta w k
w∈L(M L ) ⇔ w∈L ⇒ L = L(M L ) ⇒ L es recursivo (absurdo)
Conclusión: ∃ M HP
85

Automatas y Lenguajes

Cargado por

Copyright:

Formatos disponibles

Automatas y Lenguajes

Cargado por

Información del documento

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

Automatas y Lenguajes

Cargado por

Copyright:

Formatos disponibles

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES NICOLÁS KOVAC NEUMANN (Revisado Julio/2005)

Breve comentario introductorio

Los títulos en azul corresponden a subapartados de un determinado tema, que

Def: corresponde a una definición de algún término o términos, que aparecen

Teor: corresponde al enunciado de algún teorema.

Dem: implica el inicio de una demostración.

Agradecimientos a: David Taima Hernández por la notable mejora de los dibujos.

Espero que estos apuntes les sirvan de algo... un saludo.

Tema 1: Conceptos Previos

Tema 2: Conceptos Básicos

Tema 3: Lenguajes regulares y Autómatas Finitos

Tema 4: Gramáticas. Lenguajes Independientes del Contexto

Tema 5: Máquinas de Turing

P. ej: "3 es entero" ≡ "Ν es finito" (ambas falsas)

Cuando hablamos de una proposición condicional, de la forma p → q, a "p" se

La tabla de verdad se saca fácilmente viendo el ejemplo anterior

• Contrapuesta (¬q → ¬p)

Como se puede apreciar, la Contrapuesta es equivalente a la Condicional.

Si p y q son equivalentes, entonces p ↔ q es una tautología.

Def: Una tautología es una proposición siempre cierta.

Si p → q es una tautología, se escribe p ⇒ q

Def: Se llama p(x) a una frase abierta o función proposicional, donde

P. ej.: x² - 1 = 0. Esta ecuación depende de la variable "x".

Def: Se llama "Conjunto de significados de una variable" al conjunto de

P. ej.: Sea A = {1, 2, 3}.

Def: Se llama "Conjunto de verdad" a aquel subconjunto del conjunto

La función Conjunto de significados Conjunto de verdades

Son cuantificadores los siguientes símbolos:

Sea | (tal que)

Teor: ¬ ( ∀ x P(x)) ≡ ∃ x | ¬P(x).

Sea el conjunto de las vocales, A = {a, e, i, o, u}.

a ∈ A (a pertenece al conjunto de las vocales).

a, b ∉ Ν (a, b no pertenecen al conjunto de los números).

Teor: Dos conjuntos son iguales si contienen los mismos elementos.

Def: Se denomina cardinal de un conjunto, y se representa por |A|,

Algunas cuestiones de notación:

a ≠ {a} ; el ELEMENTO "a" es distinto al CONJUNTO que contiene "a".

Def: Existe el llamado Conjunto Vacío ( ∅ ), que es el que no tiene

Def: Se denomina Conjunto Potencia al conjunto de todos los

Def: Definición de Familia Indexada de Conjuntos.

Operaciones con conjuntos.

• Unión (A ∪ B) = {x | x∈A ∨ x∈B}

Def: A y B son disjuntos si no tienen elementos comunes, es decir, si

Def: Se llama U al conjunto universal

Def: Se define el Producto Cartesiano como:

Def: Se define una relación como:

Def: Se define el Dominio = Dom(R) = {x∈A| ∃ y∈B, (x, y)∈R}

Def: Se define la Imagen = Im(R) = {y∈B| ∃ x∈A, (x, y)∈R}

Def: Se define la partición de un conjunto como:

La unión de todos los subconjuntos de Ψ da como resultado "A",

Def: Se define Relación de Equivalencia del siguiente modo:

Esta relación tiene 3 propiedades:

Si cumple las tres propiedades, estamos hablando de una relación

Def: Se define Clase de equivalencia, como:

Teor: Las clases de equivalencia de una relación de equivalencia

Teor: Cualquier partición de un conjunto describe una relación de

Def: Se define Función Total de la siguiente manera:

Dicho de otro modo, todos los elementos de A tienen que tener

Def: Se define Función Parcial de la siguiente manera: