Fundamentos de la ciencia de la computacion

Solo disponible en BuenasTareas
  • Páginas : 227 (56728 palabras )
  • Descarga(s) : 0
  • Publicado : 22 de diciembre de 2011
Leer documento completo
Vista previa del texto
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 9 de noviembre de 2007

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 del autor.

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.

2

´ 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 13 13 15 19 21 23 25 27 28 30 31 34 39 41 41 46 47 50 52 55 57 57 59 64 66

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 de ER a AFND . . . . . . . . . . . . o 2.5 Conversi´n de AFND a AFD . . . . . . . . . . . . o 2.6 Conversi´n de AFD a ER . . . . . . . . . . . . . o 2.7 Propiedades deClausura . . . . . . . . . . . . . . 2.8 Lema de Bombeo . . . . . . . . . . . . . . . . . . 2.9 Propiedades Algor´ ıtmicas de Lenguajes Regulares 2.10 Ejercicios . . . . . . . . . . . . . . . . . . . . . . 2.11 Preguntas de Controles . . . . . . . . . . . . . . . 2.12 Proyectos . . . . . . . . . . . . . . . . . . . . . . 3 Lenguajes Libres del Contexto 3.1 Gram´ticas Libres del Contexto (GLCs) . . . a3.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.9 Determinismo y Parsing . . . . . . .. . . . . 3.10 Ejercicios . . . . . . . . . . . . . . . . . . . . 3.11 Preguntas de Controles . . . . . . . . . . . . . 3 . . . . . . . . . . . . . . . . . . . . . .

3.12 Proyectos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 M´quinas de Turing y la Tesis de Church a 4.1 La M´quina de Turing (MT) . . . . . . . . . . a 4.2 Protocolos para Usar MTs . . . . . . ....
tracking img