computacion

Teor´ıa de la Computaci´on
(Lenguajes Formales, Computabilidad y Complejidad)


Departamento de Ciencias de la Computaci´on
Universidad de Chile
gnavarro@dcc.uchile.cl
6 de noviembre de 2014

2

Licencia de uso: Esta obra est´a bajo una licencia de
Creative Commons (ver http://creativecommons.org/licenses/bync-nd/2.5/). Esencialmente, usted puede distribuir y comunicar
p´ublicamentela obra, siempre que (1) d´e cr´edito al autor de la obra,
(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´erminos de la licencia de esta obra. Estas
condiciones pueden modificarse con permiso escrito del autor.

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

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

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
..
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

5
5
6
7
10
11

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
..
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

43
43
48
49
53
54
57...