DIVISIÓN DE INGENIERÍA ELÉCTRICA
DEPARTAMENTO DE INGENIERIA EN COMPUTACIÓN


Programa de la Asignatura: 	LENGUAJES FORMALES Y AUTÓMATAS

Clave: 		0442		  Núm. de créditos:	8

Carrera:   ING. EN COMPUTACION


Duración del curso:
    		   Semanas:	16
		   Horas:	64

Semestre:		7º


Horas a la semana:
		Teoría:		 4	Obligatoria:	SI
		Prácticas:	 0	Optativa:



 OBJETIVO DEL CURSO

	El alumno describirá la teoría y la técnica para el diseño de 
lenguajes de computadora, así como los aspectos formales de la 
teoría de los lenguajes.



 TEMA

 Núm:		Nombre:						Horas

I.	INTRODUCCION.						   8

II.	GRAMATICAS REGULARES Y AUTOMATAS DE ESTADO FINITO.	  14

III.	GRAMATICAS DE CONTEXTO LIBRE Y AUTOMATAS TIPO PUSH-DOWN.  10

IV.	GRAMATICAS DE CONTEXTO SENSITIVO  Y AUTOMATAS TIPO
	PUSH-DOWN DOBLE.					   8
 
V.	GRAMATICAS DE ESTRUCTURA DE FRASE Y MAQUINA DE TURING.	  10

VI.	AUTOMATAS LINEALES CON FRONTERA.		           6

VII.	INDECIBILIDAD.						   8
								  __
				 				  64



ASIGNATURA ANTECEDENTE :


ESTRUCTURAS DISCRETAS


ASIGNATURAS CONSECUENTES :


COMPILADORES

INTELIGENCIA ARTIFICIAL



 ANTECEDENTES, OBJETIVOS Y CONTENIDOS DE LOS TEMAS

I.	INTRODUCCION.                                    

	ANTECEDENTES:  

		Estructuras Discretas.

	OBJETIVO:

		El alumno explicará los conceptos, notaciones,
                propiedades y características de la teoría de 
                lenguajes, gramáticas y autómatas.

	CONTENIDO:

		I.1   Conceptos básicos y notación.
		I.2   Definición de operaciones con lenguajes. 
		I.3   Jerarquía de Chomsky.
		I.4   Propiedades de cerradura.
		I.5   Gramáticas y lenguajes. 


II.	GRAMATICAS REGULARES Y AUTOMATAS DE ESTADO FINITO.

	ANTECEDENTES:

		Estructuras Discretas.

	OBJETIVO: 

		El alumno explicará los conceptos de autómatas
                finitos y gramáticas regulares. Formulará la 
                relación entre los autómatas finitos, los no 
                determinísticos y las gramáticas regulares.

	CONTENIDO:

		II.1   Introducción a las Gramáticas Regulares.
		II.2   Autómata finito  no-determinístico.
		II.3   Autómata finito determinístico.
		II.4   Autómata finito con movimientos.
		II.5   Lema de Bombeo.


III.	GRAMATICAS DE CONTEXTO LIBRE Y AUTOMATAS TIPO PUSH-DOWN.

	ANTECEDENTES: 

		Estructuras Discretas.


	OBJETIVO:

		El alumno analizará las gramáticas de contexto
                libre y los autómatas de tipo push-down,
                estableciendo de manera precisa  las relaciones
                existentes.

	CONTENIDO:
     
		III.1   Introducción  a las gramáticas de
                        contexto libre.
		III.2   Arboles de derivación.
		III.3   Lema del Bombeo y gramáticas de 
                        contexto libre.
		III.4   Programas, Lenguajes y Parsing.
		III.5   Introducción a los autómatas 
                        tipo Push-Down.
		III.6   Relación entre autómatas tipo Push-Down
                        y lenguajes de contexto libre.


IV.	GRAMATICAS DE CONTEXTO SENSITIVO Y AUTOMATAS
        TIPO PUSH-DOWN DOBLE. 

	ANTECEDENTES: 

	OBJETIVO:

		El alumno establecerá la relación entre las
                gramáticas de contexto sensitivo  y los autómatas
                tipo push-down doble.

	CONTENIDO:
     
		IV.1   Introducción a las gramáticas de
                       contexto sensitivo.
		IV.2   Forma Normal de Kuroda.
		IV.3   Autómata tipo Push-Down doble.


V.	GRAMATICAS DE ESTRUCTURA DE FRASE Y MAQUINA DE TURING.

	ANTECEDENTES:

	OBJETIVO:

		El alumno explicará las gramáticas de estructura
                de frase. Construirá y demostrará algoritmos en 
                la máquina de Turing.

	CONTENIDO:

		V.1   Introducción a las gramáticas de
                      estructura de frase.
		V.2   El modelo de Máquina de Turing.
		V.3   Lenguajes Computables.
		V.4   Máquina de Turing Universal.
		V.5   Variaciones de la Máquina de Turing.


VI.	AUTOMATAS LINEALES CON FRONTERA.

	ANTECEDENTES: 

	OBJETIVO:

		El alumno comprenderá la teoría y aplicaciones de
                los autómatas lineales con frontera.

	CONTENIDO:

		VI.1   Introducción.
		VI.2   Autómata lineal con frontera.


VII.	INDECIBILIDAD.

	ANTECEDENTES:

	OBJETIVO:

		El alumno usará la recursividad en los lenguajes
                y explicará el concepto de problemas indecidibles.

	CONTENIDO:

		VII.1	Indecibilidad.
		VII.2	Lenguajes recursivos y recursivos 
                        enumerables.
		VII.3	Tesis de Church-Turing y problemas 
                        indecidibles.
		VII.4	Teorema de Rice y problemas indecidibles.
		VII.5	Problema de correspondencia de post e
                        indecibilidad.
		VII.6	"Halting Problem" e indecibilidad.



TECNICAS DE ENSEÑANZA:			ELEMENTOS DE EVALUACION:
 
Exposición oral			  (X)	Exámenes parciales		 (X)
Exposición audiovisual		  (X)	Exámenes finales		 (X)
Ejercicios dentro de clase	  (X)	Trabajos y tareas fuera del aula (X)
Ejercicios fuera del aula	  (X)	Participación en clase		 (X)
Seminarios			  ( )	Asistencia a prácticas		 ( )
Lecturas obligatorias		  (X)	Otros:
Trabajo de investigación	  (X)
Prácticas de taller o laboratorio ( )
Prácticas de campo		  ( )
Otras:



BIBLIOGRAFIA

 TEXTOS BASICOS		Temas de la materia para los que se recomienda:


	HOPCROFT AND ULLMAN               	Todos
	"Formal languages and their relation to automata"
	Addison Wesley, E.E.U.U., 1969


	HOPCROFT AND ULLMAN        		Todos
	"Introduction to automata theory,languages and computation"
	Addison Wesley, E.E.U.U., 1979


	MINSKY, M.                      	Todos
	"Computation: Finite and infinite machines"
	Prentice-Hall, E.E.U.U., 1967


	PRESSER-CARDENAS Y MARIN       		III
	"Ciencias de la Computación, Vol II"
	Limusa, México, 1983


	ARBIB, M.A.                             Todos
	"Theories of abstract automata"
	Prentice-Hall, E.E.U.U., 1969


	NELSON, R.J               		Todos
	"Introduction to automata"
	Wiley, E.E.U.U., 1968


	KAIN, R.Y                               Todos
	"Automata theory: machines and languages"
	Mc Graw Hill, E.E.U.U., 1972