notas cc9

Teoría de la Computación

TEORÍA DE LA COMPUTACIÓN (CC209)
AUTOR: MTRO. GÓMEZ ANDRADE ABELARDO
e-mail: abelardo.gomez@red.cucei.udg.mx

ATENCIÓN: Se recomienda al alumno que lea detenidamente el programa de la materia
incluido en el apéndice 1 de este documento, ya que contiene información adicional
demasiado importante, tal como los criterios de evaluación. Es mejor detenerse unosminutos y aclarar dudas en este momento, que tener problemas de interpretación al
final del curso (¡¡¡y reprobarlo!!!).

COMENTARIOS PRELIMINARES
Aunque aparezca como único prerrequisito de este curso la asignatura de Matemáticas
Discretas, hay que advertir al alumno de que requiere tener un dominio sobre los temas que
aprendió en algunos cursos anteriores, destacando sobre todo, en materias comoLógica y
Conjuntos, Introducción a la Computación, Introducción a la Programación Estructurada
(curso y taller), Estructura de Datos o Sistemas Digitales.
También es importante comentar que los conceptos que se habrán de recibir en esta
asignatura, le serán de utilidad al cursar materias, tanto de las que es prerrequisito como
Compiladores o Análisis y Diseño de Algoritmos, como de otras queno están incluidas en la
Seriación.
Es necesario que el profesor de la asignatura les aclare a los alumnos que la misma se
imparte en muchas ocasiones bajo un criterio exclusivamente matemático, sin que se vea
cómo se aplicará computacionalmente. Se debe pedir paciencia al estudiante, y aclararle que
sin conocer el fundamento matemático, no podrá interpretar el significado de lo que seestará
estudiando. El compromiso es que al avanzar en el ciclo escolar, lo pueda descubrir.
Se recomienda hacer una sesión introductoria en la que se hable de los siguientes temas:
1. Relación de las Matemáticas con las ciencias computacionales.
2. Problemática de la enseñanza de la Matemática.
3. Los modelos matemáticos como una representación de la realidad.
4. Simulación y su importancia.
5.¿Cuál es, en realidad, el cómputo avanzado?
6. ¿Es posible ser un profesional de la computación sin dominar las matemáticas?

Página 1

Teoría de la Computación

MÓDULO I
GRAMÁTICAS Y LENGUAJES FORMALES
CONCEPTOS INTRODUCTORIOS
Considérense las siguientes definiciones iniciales como punto de partida para
especificar los conceptos que habrán de estudiarse en este primer módulo. Lostérminos son un poco abstractos y no debe preocuparse el lector si en este momento
le parece que no es claro lo que se pretende expresar con ellos. Al avanzar en el curso
se irán entendiendo mejor.
TEORÍA DE LOS LENGUAJES FORMALES: Estudio de los Lenguajes Formales. Una rama
importante de esta teoría se ocupa de la descripción finita de Lenguajes infinitos. Esta
representación adopta la forma de unmecanismo abstracto para generar o reconocer
cualquier cadena del Lenguaje (llamada Gramática). Esta rama se aplica a la sintaxis de los
Lenguajes de programación (en cuanto son distintos de su semántica, que requiere
elementos de trabajo bastante diferentes). Así, el conjunto de todos los programas válidos de
Pascal o de C, puede considerarse como un Lenguaje Formal sobre el alfabeto desímbolos
de Pascal, o de C respectivamente.
LENGUAJE FORMAL: Lenguaje con reglas explícitas y precisas para su sintaxis y
semántica. Como ejemplo se pueden citar los lenguajes de programación y también lógica
como el cálculo de predicados. Así, los Lenguajes Formales se distinguen de los naturales
tales como el castellano, cuyas reglas a medida que evolucionan con el uso dejan de ser unadefinición completa o precisa de la sintaxis del lenguaje y mucho menos de su semántica.
GRAMÁTICA FORMAL: Es un esquema generativo para la representación finita de los
lenguajes, es decir, un solo modelo dinámico para generar palabras o cadenas de un
lenguaje. Es la manera principal de especificar un Lenguaje Formal aunque sea infinito por
medios finitos. Los Lenguajes pueden ser finitos o...