Teoria Computacion
READ PAPER
Teoria Computacion
Teoria Computacion
Loading Preview
scribd. scribd. scribd. scribd. scribd. scribd. scribd. scribd. scribd. scribd. scribd. scribd. scribd. scribd. scribd. scribd. scribd. scribd. scribd. scribd.
INSTITUTO TECNOLÓGICO de Celaya.
“TEORÍA DE LA COMPUTACIÓN” LIBRO DE TEXTO QUE PARA OBTENER EL TITULO DE: INGENIERO EN SISTEMAS COMPUTACIONALES PRESENTA: ADRIANA ACEVEDO JUÁREZ Celaya, Gto. Junio 2006.
DEDICATORIAS
A DIOS Nuestro creador, por permitirme ver la luz de cada nuevo día, por ser la base de mi fe, por ser mi amigo incondicional en toda ocasión de alegría o tristeza y el pilar de mi existencia. A MI MADRE Quien me sustento, cuido, alentó y motivo en todo momento. Gracias mamá, por el gran cariño con el que me formaste, todos los principios que me inculcaste y sobre todo el AMOR con el que me cubriste en todo instante de mi vida. A MI PADRE Por haberme hecho fuerte, por alentarme y empujarme a enfrentar la vida apoyándome moral y espiritualmente. A MIS HERMANAS Y MI CUÑADO A mis hermanas, por ser mis compañeras de juegos y mis cómplices de travesuras, por que su compañía es uno de los mejores regalos que me ha brindado la vida. A mi cuñado, por la amistad y el apoyo que me ha brindado en el transcurso y culminación de mis estudios. A JAIME Por el cariño brindado, por esas largas horas de compañía, por su apoyo en todo el transcurso de mi carrera. Gracias por todo tu AMOR.
A MIS AMIGOS Por su apoyo y compañerismo, por esos momentos de alegrías y esos momentos de trabajo. Por los logros obtenidos en el grupo, por mostrarme que la vida también requiere de tiempo para uno mismo, y no solo de trabajo. A MIS MAESTROS Por ser parte de mi formación profesional y humana. En especial a mi asesora M. C. Maria de Jesús Hernández Morales por el apoyo brindado en la realización de este trabajo.
CUANDO LAS COSAS DE LA VIDA PARECEN DEMASIADO Y LAS 24 HORAS DEL DÍA NO SON SUFICIENTE, SIEMPRE HAY ESPACIO PARA UNA TAZA DE CAFÉ. Un profesor, delante de su clase de filosofía, sin decir palabra, tomo un frasco grande y vació de mayonesa y procedió llenarlo con pelotas de golf. Luego, le pregunto a sus estudiantes si el frasco estaba lleno los estudiantes estuvieron de acuerdo en decir que si. Así que el maestro tomo una caja llena de canicas y la vació dentro del frasco de mayonesa .las canicas llenaron los espacios vacíos entre las pelotas de golf el profesor volvió a preguntarles a los estudiantes si el frasco estaba lleno y ellos volvieron a decir que si. Luego el maestro tomo una caja de arena y la vació dentro del frasco, por supuesto, la arena lleno todos los espacios vacíos y el profesor cuestiono nuevamente si el frasco estaba lleno. En esta ocasión los estudiantes respondieron con un si unánime. El profesor enseguida agrego dos tazas de aromático café diluido en agua al contenido del frasco, con lo que efectivamente, el líquido llenaría todos los espacios vacíos entre la arena. Los estudiantes reían en esta ocasión. Cuando la risa se apagaba, el maestro comento: "Quiero que se den cuenta que este frasco representa la vida, las pelotas de golf son las cosas importantes, como dios, la familia, los hijos, la salud, los amigos, las cosas que te apasionan. Son cosas que incluso si todo lo demás lo perdiéramos y solo estas quedaran, nuestras vidas aun estarían llenas. Las canicas son las otras cosas que importan, como el trabajo, la casa, el carro, etc. la arena es todo lo demás, las pequeñas cosas...si ponemos la arena en el frasco primero, no habría espacio para las canicas ni para las pelotas de golf. Lo mismo ocurre con la vida. Si gastamos todo nuestro tiempo y energía en las cosas pequeñas, nunca tendremos lugar para las que realmente son importantes...
así que presta atención a las cosas que son cruciales para tu felicidad. Juega con tus hijos, tomate tiempo para asistir al doctor, ve con tu pareja a cenar, practica tu deporte favorito o afición favorita. Siempre habrá tiempo para limpiar la casa y reparar la llave del agua... ocúpate de las pelotas de golf primero, es decir de las cosas que real mente importan... establece tus prioridades, el resto es sola arena". Uno de los estudiantes levanto la mano y pregunto que representaba el café. El profesor sonrió y dijo: que bueno que lo preguntas. Solo es para demostrarles que no importa cuan ocupada tu vida pueda parecer, siempre hay lugar para un par de tazas de café con un buen amigo!
DEDICATORIAS
A DIOS Nuestro creador, por permitirme ver la luz de cada nuevo día, por ser la base de mi fe, por ser mi amigo incondicional en toda ocasión de alegría o tristeza y el pilar de mi existencia. A MI MADRE Quien me sustento, cuido, alentó y motivo en todo momento. Gracias mamá, por el gran cariño con el que me formaste, todos los principios que me inculcaste y sobre todo el AMOR con el que me cubriste en todo instante de mi vida. A MI PADRE Por haberme hecho fuerte, por alentarme y empujarme a enfrentar la vida apoyándome moral y espiritualmente. A MIS HERMANAS Y MI CUÑADO A mis hermanas, por ser mis compañeras de juegos y mis cómplices de travesuras, por que su compañía es uno de los mejores regalos que me ha brindado la vida. A mi cuñado, por la amistad y el apoyo que me ha brindado en el transcurso y culminación de mis estudios. A JAIME Por el cariño brindado, por esas largas horas de compañía, por su apoyo en todo el transcurso de mi carrera. Gracias por todo tu AMOR.
A MIS AMIGOS Por su apoyo y compañerismo, por esos momentos de alegrías y esos momentos de trabajo. Por los logros obtenidos en el grupo, por mostrarme que la vida también requiere de tiempo para uno mismo, y no solo de trabajo. A MIS MAESTROS Por ser parte de mi formación profesional y humana. En especial a mi asesora M. C. Maria de Jesús Hernández Morales por el apoyo brindado en la realización de este trabajo.
CUANDO LAS COSAS DE LA VIDA PARECEN DEMASIADO Y LAS 24 HORAS DEL DÍA NO SON SUFICIENTE, SIEMPRE HAY ESPACIO PARA UNA TAZA DE CAFÉ. Un profesor, delante de su clase de filosofía, sin decir palabra, tomo un frasco grande y vació de mayonesa y procedió llenarlo con pelotas de golf. Luego, le pregunto a sus estudiantes si el frasco estaba lleno los estudiantes estuvieron de acuerdo en decir que si. Así que el maestro tomo una caja llena de canicas y la vació dentro del frasco de mayonesa .las canicas llenaron los espacios vacíos entre las pelotas de golf el profesor volvió a preguntarles a los estudiantes si el frasco estaba lleno y ellos volvieron a decir que si. Luego el maestro tomo una caja de arena y la vació dentro del frasco, por supuesto, la arena lleno todos los espacios vacíos y el profesor cuestiono nuevamente si el frasco estaba lleno. En esta ocasión los estudiantes respondieron con un si unánime. El profesor enseguida agrego dos tazas de aromático café diluido en agua al contenido del frasco, con lo que efectivamente, el líquido llenaría todos los espacios vacíos entre la arena. Los estudiantes reían en esta ocasión. Cuando la risa se apagaba, el maestro comento: "Quiero que se den cuenta que este frasco representa la vida, las pelotas de golf son las cosas importantes, como dios, la familia, los hijos, la salud, los amigos, las cosas que te apasionan. Son cosas que incluso si todo lo demás lo perdiéramos y solo estas quedaran, nuestras vidas aun estarían llenas. Las canicas son las otras cosas que importan, como el trabajo, la casa, el carro, etc. la arena es todo lo demás, las pequeñas cosas...si ponemos la arena en el frasco primero, no habría espacio para las canicas ni para las pelotas de golf. Lo mismo ocurre con la vida. Si gastamos todo nuestro tiempo y energía en las cosas pequeñas, nunca tendremos lugar para las que realmente son importantes... así que presta atención a las cosas que son cruciales para tu felicidad. Juega con tus
hijos, tomate tiempo para asistir al doctor, ve con tu pareja a cenar, practica tu deporte favorito o afición favorita. Siempre habrá tiempo para limpiar la casa y reparar la llave del agua... ocúpate de las pelotas de golf primero, es decir de las cosas que real mente importan... establece tus prioridades, el resto es sola arena". Uno de los estudiantes levanto la mano y pregunto que representaba el café. El profesor sonrió y dijo: que bueno que lo preguntas. Solo es para demostrarles que no importa cuan ocupada tu vida pueda parecer, siempre hay lugar para un par de tazas de café con un buen amigo!
Instituto Tecnológico de Celaya Teoría de la Computación I
ANTECEDENTES
Cada ser humano pasa por varios periodos o etapas en su vida, cada una de ellas con un grado de prioridad y de importancia; una de éstas es la etapa estudiantil y en algunos casos, ésta se termina al culminar sus estudios universitarios y obtener un título de acuerdo a la carrera que se haya elegido. En el transcurso estudiantil el alumno se enfrenta a varias adversidades; como la falta de material didáctico que le ayude a investigar y reafirmar los conocimientos obtenidos en cada materia. Uno de estos casos es el de la materia “Teoría de la Computación”; cuya falta de textos didácticos completos, que guíen al alumno en su transcurso por ésta, pueden afectar su rendimiento. Tal situación, es una de las causas por las cuales se desea desarrollar un texto didáctico que oriente al estudiante en el desarrollo de esta materia. Por otra parte, otro propósito por lo cual se desea llevar a cabo este proyecto es el de concluir con los estudios académicos para obtener el grado de Ingeniero en Sistemas Computacionales.
Instituto Tecnológico de Celaya Teoría de la Computación II
OBJETIVO GENERAL
Desarrollar un texto didáctico de tipo teórico-práctico que ayude al estudiante a comprender la base para la construcción de sistemas formales que se imparten en la materia “Teoría de la Computación”.
OBJETIVOS ESPECÍFICOS
♦
Fortalecer el aprendizaje del alumno al contar con un texto didáctico de apoyo, enfocado totalmente a la materia que se cursa.
♦
Integrar el mejor material de texto que exista actualmente en las diferentes fuentes bibliográficas de la materia, en un material accesible para el estudiante.
♦
Desarrollar un texto didáctico de fácil comprensión para el estudiante.
♦
Desarrollar un texto didáctico cuya índole llame la atención del estudiante aumentando su interés por la materia.
♦
Desarrollar ejercicios prácticos que ayuden al estudiante a fortalecer la teoría plateada en esta materia.
Instituto Tecnológico de Celaya Teoría de la Computación III
JUSTIFICACIÓN
La falta de material didácticos que guíen al alumno de manera completa en los temas que abarca la materia “Teoría de la Computación”, es un problema que afecta directamente a los alumnos del Instituto Tecnológico de Celaya, ya que el alumno suele tener perdidas de tiempo en la búsqueda de material que pueda ayudarle en el estudio de esta materia; material que muchas veces no es encontrado; tal situación ha llevado a pensar en desarrollar un libro de texto que ayude al alumno en el curso de esta materia mejorando su rendimiento y por consecuencia moldeando mejores Ingenieros en Sistemas Computacionales.
Instituto Tecnológico de Celaya Teoría de la Computación IV
ÍNDICE
Antecedentes I Objetivo General II Objetivos Específicos II Justificación III Introducción general VIII
UNIDAD 1. INTRODUCCIÓN
Objetivo 1 Diagrama temático de la unidad 2 1.
Introducción 3
1.1
Introducción
3
1.2
Nociones matemáticas.
4
1.2.1
Conjuntos
4
1.2.2
Funciones y relaciones
11
1.2.3
Cadenas y lenguajes
18
1.3
Inducción matemática.
25
1.4 Autómatas, Computabilidad y Complejidad
27 Resumen 28 Glosario 32 Ejercicios 36 Problemas 37 Lectura complementaría 39 Bibliografía 41 Retroalimentación 42
UNIDAD 2. LENGUAJES REGULARES
Objetivo 44 Diagrama temático de la unidad 45 2.
LENGUAJES REGULARES 46
2.1
Introducción
46
Instituto Tecnológico de Celaya Teoría de la Computación V
2.2
Autómatas finitos
47
2.2.1
Jerarquía de Chomsky
48
2.2.2
Autómatas finitos determinísticos.
53
2.2.3
Autómatas finitos no determinísticos.
56
2.3
Expresiones regulares.
62
2.4
Lenguajes no regulares.
64 Resumen 66 Glosario 71 Ejercicios 74 Problemas 75 Lectura complementaría 77 Bibliografía 80 Retroalimentación 81
UNIDAD 3. LENGUAJES INDEPENDIENTES DEL CONTEXTO
Objetivo 84 Diagrama temático de la unidad 85 3.
LENGUAJES LIBRES DE CONTEXTO. 86
3.1
Introducción.
86
3.2
Gramáticas libres de contexto.
87
3.2.1
Construcción de gramáticas
87
3.3
Árboles de derivación.
90
3.4
Formas normales de Chomsky,
93
3.4.1
Algoritmos de eliminación de producciones inútiles.
94
3.4.2
Algoritmos de eliminación de producciones anulables
97
3.4.3
Algoritmos de eliminación de producciones unitarias
100
3.5
Formas normales de Greibach.
104
3.6
Eliminación de Factores Comunes izquierdos.
106
3.7
Eliminación de recursividad izquierda.
108
3.8
Eliminación de la ambigüedad.
111
3.9
Autómatas Push-Down.
111
3.9.1
AP y gramáticas independientes del contexto.
114
Instituto Tecnológico de Celaya Teoría de la Computación VI
Resumen 118 Glosario 124 Ejercicios 125 Problemas 126 Lectura complementaría 128 Bibliografía 130 Retroalimentación 131
UNIDAD 4. MÁQUINAS DE TURING
Objetivo 134 Diagrama temático de la unidad 135 4.
MÁQUINA DE TURING. 136
4.1
Introducción.
136
4.2
Conceptos básicos
137
4.2.1
Definición formal de una máquina de Turing
138
4.3
Construcción modular de una máquina de Turing.
140
4.3.1
Bloques básicos
141
4.4
Lenguajes aceptados por la MT.
144
4.5
Variantes de una máquina de Turing.
145
4.5.1
Permanencia
145
4.5.2
Subceldas
146
4.5.3
Cinta finita
146
4.5.4
Multicitas
147
4.5.5
MT no determinística
148
4.6
Problemas de Hilbert
149 Resumen 151 Glosario 155 Ejercicios 156 Problemas 157 Lectura complementaría 158 Bibliografía 166 Retroalimentación 167
Instituto Tecnológico de Celaya Teoría de la Computación VII
UNIDAD 5. DECIDIBILIDAD
Objetivo 172 Diagrama temático de la unidad 173 5.
DECIBILIDAD 174
5.1
Introducción.
174
5.2
Lenguajes decidibles
175
5.3
El problema de Halting.
177
5.4
Decidibilidad de teorías lógicas.
179 Resumen 181 Glosario 183 Ejercicios 184 Lectura complementaría 185 Bibliografía 191 Retroalimentación 192
UNIDAD 6. REDUCIBILIDAD
Objetivo 193 Diagrama temático de la unidad 194 6.
REDUCIBILIDAD. 195
6.1
Introducción
195
6.2
Problemas insolubles para la teoría de lenguajes.
196
6.3
Un problema simple insoluble.
197
6.4
Funciones computables.
199
6.5
Reducibilidad de Turing.
201 Resumen 202 Glosario 204 Ejercicios 205 Lectura complementaría 206 Bibliografía 207 Retroalimentación 208 Anexos Conclusiones
Sorry, preview is currently unavailable. You can download the paper by clicking the button above.