Apuntes teoria de la computacion
Páginas: 86 (21296 palabras)
Publicado: 9 de noviembre de 2011
Cuadernillo de apuntes Teor´ de la ıa computaci´n o
Magaly Gonz´lez Mota a 30 de junio de 2010
2
´ Indice general
1. INTRODUCCION 1.1. Aut´matas computabilidad y complejidad o 1.1.1. Representaciones estructurales . . . 1.1.2. Aut´matas y la complejidad . . . . o 1.2. Nociones Matem´ticas . . . . . . . . . . . a 1.2.1. Conjuntos . . . . . . . . . . . . . . 1.2.2. Funciones y relaciones. . . . . . . 1.2.3. Inducci´n matem´tica . . . . . . . o a 1.3. Cadenas y lenguajes . . . . . . . . . . . . 2. Lenguajes regulares 2.1. Aut´matas finitos . . . . o 2.1.1. Aut´matas finitos o 2.1.2. Aut´matas finitos o 2.2. Expresiones regulares . . 2.3. Lenguajes Regulares . . 5 5 7 7 7 7 12 17 19 25 25 26 29 31 35 37 37 41 45 45 46 47 55
. . . . . . . .
. . . . . . . .
. . . . . . . .
.. . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . . . . . . . . . deterministicos AFD . . . no deterministicos AFND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
3. Lenguajes libres decontexto 3.1. Gram´ticas libres de contexto a ´ 3.2. Arboles de derivaci´n . . . . . o 3.3. Formas normales de Comsky . 3.4. Forma normal de Greibach . . 3.5. Ambig¨edad . . . . . . . . . . u 3.6. Aut´matas de Pila . . . . . . o 3.7. Lenguajes no regulales . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
.. . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
4. M´quinas de Turing a 61 4.1. Definici´n de una M´quina de Turing . . . . . . . . . . . . . . 63 o a 3
4 4.2. Construcci´n modular de una MT . . . . . . o 4.3. El lenguaje de una M´quina de Turing . . . a 4.4. Variantes de unaM´quina de Turing . . . . a 4.4.1. M´quina de Turing con varias cintas a 4.4.2. M´quinas con pilas multiples . . . . a 4.4.3. M´quinas contadoras . . . . . . . . . a . . . . . .
´ INDICE GENERAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 70 71 71 72 73 77 78 79 80 83 83 85 85 88
5. Decibilidad 5.1. Lenguajes Decidibles . .. . . . . . . . . . . . . . . . . . . . . 5.2. El problema de Halting . . . . . . . . . . . . . . . . . . . . . . 5.3. Decibilidad de teor´ l´gicas . . . . . . . . . . . . . . . . . . . ıas o 6. Reducibilidad 6.1. Problemas insolubles para la teor´ de lenguajes ıa 6.2. Un problema simple insoluble . . . . . . . . . . 6.2.1. Algoritmo de Kruskal . . . . . . . . . . . 6.3. Funciones computables . .. . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
Cap´ ıtulo 1 INTRODUCCION
Objetivo de la Unidad Situar la importancia del estudio de los aut´matas dentro del proceso de desarrollo de software, y algunas aplicao ciones. Presentar las nociones b´sicas de matem´ticas necesarias para comena a zar a estudiar la materia.
1.1.Aut´matas computabilidad y complejio dad
Se conoce como teor´a de aut´matas el estudio de las m´quinas o disposı o a itivos abstractos con capacidad de computaci´n. o En la decada de 1930 el matem´tico ingles Alan Mathison Turing estudi´ una a o m´quina con el objetivo de determinar con presici´n cu´l era la frontera entre a o a lo que podia o no pod´ hacer una m´quina computadora. ıa a En lasdecadas de 1940 y 1950 se estudiar´n otro tipo de m´quinas o a sencillas conocidas con el nombre de aut´matas finitos, los cuales inicialo mente pretendian modelar las funciones cerebrales. A finales de la decada de 1950 el ling¨ista estadounidense Noam Chomsky comenz´ el estudio de las u o gram´ticas formales, las cuales no son m´quinas, pero son componentes de a a software importantes por su...
Magaly Gonz´lez Mota a 30 de junio de 2010
2
´ Indice general
1. INTRODUCCION 1.1. Aut´matas computabilidad y complejidad o 1.1.1. Representaciones estructurales . . . 1.1.2. Aut´matas y la complejidad . . . . o 1.2. Nociones Matem´ticas . . . . . . . . . . . a 1.2.1. Conjuntos . . . . . . . . . . . . . . 1.2.2. Funciones y relaciones. . . . . . . 1.2.3. Inducci´n matem´tica . . . . . . . o a 1.3. Cadenas y lenguajes . . . . . . . . . . . . 2. Lenguajes regulares 2.1. Aut´matas finitos . . . . o 2.1.1. Aut´matas finitos o 2.1.2. Aut´matas finitos o 2.2. Expresiones regulares . . 2.3. Lenguajes Regulares . . 5 5 7 7 7 7 12 17 19 25 25 26 29 31 35 37 37 41 45 45 46 47 55
. . . . . . . .
. . . . . . . .
. . . . . . . .
.. . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . . . . . . . . . deterministicos AFD . . . no deterministicos AFND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
3. Lenguajes libres decontexto 3.1. Gram´ticas libres de contexto a ´ 3.2. Arboles de derivaci´n . . . . . o 3.3. Formas normales de Comsky . 3.4. Forma normal de Greibach . . 3.5. Ambig¨edad . . . . . . . . . . u 3.6. Aut´matas de Pila . . . . . . o 3.7. Lenguajes no regulales . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
.. . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
4. M´quinas de Turing a 61 4.1. Definici´n de una M´quina de Turing . . . . . . . . . . . . . . 63 o a 3
4 4.2. Construcci´n modular de una MT . . . . . . o 4.3. El lenguaje de una M´quina de Turing . . . a 4.4. Variantes de unaM´quina de Turing . . . . a 4.4.1. M´quina de Turing con varias cintas a 4.4.2. M´quinas con pilas multiples . . . . a 4.4.3. M´quinas contadoras . . . . . . . . . a . . . . . .
´ INDICE GENERAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 70 71 71 72 73 77 78 79 80 83 83 85 85 88
5. Decibilidad 5.1. Lenguajes Decidibles . .. . . . . . . . . . . . . . . . . . . . . 5.2. El problema de Halting . . . . . . . . . . . . . . . . . . . . . . 5.3. Decibilidad de teor´ l´gicas . . . . . . . . . . . . . . . . . . . ıas o 6. Reducibilidad 6.1. Problemas insolubles para la teor´ de lenguajes ıa 6.2. Un problema simple insoluble . . . . . . . . . . 6.2.1. Algoritmo de Kruskal . . . . . . . . . . . 6.3. Funciones computables . .. . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
Cap´ ıtulo 1 INTRODUCCION
Objetivo de la Unidad Situar la importancia del estudio de los aut´matas dentro del proceso de desarrollo de software, y algunas aplicao ciones. Presentar las nociones b´sicas de matem´ticas necesarias para comena a zar a estudiar la materia.
1.1.Aut´matas computabilidad y complejio dad
Se conoce como teor´a de aut´matas el estudio de las m´quinas o disposı o a itivos abstractos con capacidad de computaci´n. o En la decada de 1930 el matem´tico ingles Alan Mathison Turing estudi´ una a o m´quina con el objetivo de determinar con presici´n cu´l era la frontera entre a o a lo que podia o no pod´ hacer una m´quina computadora. ıa a En lasdecadas de 1940 y 1950 se estudiar´n otro tipo de m´quinas o a sencillas conocidas con el nombre de aut´matas finitos, los cuales inicialo mente pretendian modelar las funciones cerebrales. A finales de la decada de 1950 el ling¨ista estadounidense Noam Chomsky comenz´ el estudio de las u o gram´ticas formales, las cuales no son m´quinas, pero son componentes de a a software importantes por su...
Leer documento completo
Regístrate para leer el documento completo.