Teoria de la computacion

Fundamentos de la Ciencia de la Computaci´n
o
(Lenguajes Formales, Computabilidad y Complejidad)

Apuntes y Ejercicios

Gonzalo Navarro
Departamento de Ciencias de la Computaci´n
o
Universidad de Chile
gnavarro@dcc.uchile.cl
21 de octubre de 2008

2

Licencia de uso: Esta obra est´ bajo una licencia de
a
Creative Commons (ver http://creativecommons.org/licenses/bync-nd/2.5/).Esencialmente, usted puede distribuir y comunicar
p´blicamente la obra, siempre que (1) d´ cr´dito al autor de la obra,
u
e e
(2) no la use para fines comerciales, (3) no la altere, transforme, o
genere una obra derivada de ella. Al reutilizar o distribuir la obra,
debe dejar bien claro los t´rminos de la licencia de esta obra. Estas
e
condiciones pueden modificarse con permiso escrito delautor.

Asimismo,
agradecer´ enviar un email al autor,
e
gnavarro@dcc.uchile.cl, si utiliza esta obra fuera del Departamento
de Ciencias de la Computaci´n de la Universidad de Chile, para mis
o
registros. Finalmente, toda sugerencia sobre el contenido, errores,
omisiones, etc. es bienvenida al mismo email.

´
Indice General
1 Conceptos B´sicos
a
1.1 Inducci´n Estructural . . . . . . ..
o
1.2 Conjuntos, Relaciones y Funciones
1.3 Cardinalidad . . . . . . . . . . . .
1.4 Alfabetos, Cadenas y Lenguajes . .
1.5 Especificaci´n Finita de Lenguajes
o

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
..
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

5
5
6
7
10
11

2 Lenguajes Regulares
2.1 Expresiones Regulares (ERs) . . . . . . . . . . . .
2.2 Aut´matas Finitos Determin´
o
ısticos (AFDs) . . . .
2.3 Aut´matas Finitos No Determin´
o
ısticos (AFNDs) .
2.4 Conversi´n deER a AFND . . . . . . . . . . . .
o
2.5 Conversi´n de AFND a AFD . . . . . . . . . . . .
o
2.6 Conversi´n de AFD a ER . . . . . . . . . . . . .
o
2.7 Propiedades de Clausura . . . . . . . . . . . . . .
2.8 Lema de Bombeo . . . . . . . . . . . . . . . . . .
2.9 Propiedades Algor´
ıtmicas de Lenguajes Regulares
2.10 Ejercicios . . . . . . . . . . . . . . . . . . . . . .
2.11 Preguntas deControles . . . . . . . . . . . . . . .
2.12 Proyectos . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
..
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

13
13
15
20
22
24
26
28
29
31
32
35
40

3 Lenguajes Libres del Contexto
3.1 Gram´ticas Libres del Contexto(GLCs) . . .
a
3.2 Todo Lenguaje Regular es Libre del Contexto
3.3 Aut´matas de Pila (AP) . . . . . . . . . . . .
o
3.4 Conversi´n de GLC a AP . . . . . . . . . . .
o
3.5 Conversi´n a AP a GLC . . . . . . . . . . . .
o
3.6 Teorema de Bombeo . . . . . . . . . . . . . .
3.7 Propiedades de Clausura . . . . . . . . . . . .
3.8 Propiedades Algor´
ıtmicas . . . . . . . . . . . .
3.9Determinismo y Parsing . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
....