teoria de la computacion

Cuadernillo de apuntes Teora de la
computacion
Magaly Gonzalez Mota
30 de junio de 2010
2
Indice general
1. INTRODUCCION 5
1.1. Automatas computabilidad y complejidad . . . . . . . . . . . 5
1.1.1. Representaciones estructurales . . . . . . . . . . . . . . 7
1.1.2. Automatas y la complejidad . . . . . . . . . . . . . . . 7
1.2. Nociones Matematicas . . . . . . . . . . . . . . .. . . . . . . 7
1.2.1. Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2. Funciones y relaciones . . . . . . . . . . . . . . . . . . 12
1.2.3. Induccion matematica . . . . . . . . . . . . . . . . . . 17
1.3. Cadenas y lenguajes . . . . . . . . . . . . . . . . . . . . . . . 19
2. Lenguajes regulares 25
2.1. Automatas nitos . . . . . . . . . . . . . . . . . . . . . . . .. 25
2.1.1. Automatas nitos deterministicos AFD . . . . . . . . . 26
2.1.2. Automatas nitos no deterministicos AFND . . . . . . 29
2.2. Expresiones regulares . . . . . . . . . . . . . . . . . . . . . . . 31
2.3. Lenguajes Regulares . . . . . . . . . . . . . . . . . . . . . . . 35
3. Lenguajes libres de contexto 37
3.1. Gramaticas libres de contexto . . . . . . . . . . . . . . . . . . 373.2. Arboles de derivacion . . . . . . . . . . . . . . . . . . . . . . . 41
3.3. Formas normales de Comsky . . . . . . . . . . . . . . . . . . . 45
3.4. Forma normal de Greibach . . . . . . . . . . . . . . . . . . . . 45
3.5. Ambiguedad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.6. Automatas de Pila . . . . . . . . . . . . . . . . . . . . . . . . 47
3.7. Lenguajes noregulales . . . . . . . . . . . . . . . . . . . . . . 55
4. Maquinas de Turing 61
4.1. Denicion de una Maquina de Turing . . . . . . . . . . . . . . 63
3
4 INDICE GENERAL
4.2. Construccion modular de una MT . . . . . . . . . . . . . . . . 66
4.3. El lenguaje de una Maquina de Turing . . . . . . . . . . . . . 70
4.4. Variantes de una Maquina de Turing . . . . . . . . . . . . . . 714.4.1. Maquina de Turing con varias cintas . . . . . . . . . . 71
4.4.2. Maquinas con pilas multiples . . . . . . . . . . . . . . 72
4.4.3. Maquinas contadoras . . . . . . . . . . . . . . . . . . . 73
5. Decibilidad 77
5.1. Lenguajes Decidibles . . . . . . . . . . . . . . . . . . . . . . . 78
5.2. El problema de Halting . . . . . . . . . . . . . . . . . . . . . . 79
5.3. Decibilidad deteoras logicas . . . . . . . . . . . . . . . . . . . 80
6. Reducibilidad 83
6.1. Problemas insolubles para la teora de lenguajes . . . . . . . . 83
6.2. Un problema simple insoluble . . . . . . . . . . . . . . . . . . 85
6.2.1. Algoritmo de Kruskal . . . . . . . . . . . . . . . . . . . 85
6.3. Funciones computables . . . . . . . . . . . . . . . . . . . . . . 88
Captulo 1
INTRODUCCIONObjetivo de la Unidad Situar la importancia del estudio de los
automatas dentro del proceso de desarrollo de software, y algunas aplicaciones.
Presentar las nociones basicas de matematicas necesarias para comenzar
a estudiar la materia.
1.1. Automatas computabilidad y complejidad
Se conoce como teora de automatas el estudio de las maquinas o dispositivos
abstractos con capacidad decomputacion.
En la decada de 1930 el matematico ingles Alan Mathison Turing estudio una
maquina con el objetivo de determinar con presicion cual era la frontera entre
lo que podia o no poda hacer una maquina computadora.
En las decadas de 1940 y 1950 se estudiaron otro tipo de maquinas
sencillas conocidas con el nombre de automatas nitos, los cuales inicialmente
pretendian modelarlas funciones cerebrales. A nales de la decada de
1950 el linguista estadounidense Noam Chomsky comenzo el estudio de las
gramaticas formales, las cuales no son maquinas, pero son componentes de
software importantes por su relacion con los automatas abstractos. En 1969
el matematico estadounidense Stephen Arthur Cook separo los problemas
que se pueden resolver de manera eciente en...