Guia docente
DATOS IDENTIFICATIVOS 2011_12
Asignatura TEORIA DE AUTOMATAS Y LENG.FORMALES Código 00702009
Enseñanza
INGENIERO EN INFORMATICA
Descriptores Cr.totales Tipo Curso Semestre
12 Troncal Segundo Anual
Idioma
Prerrequisitos
Departamento MATEMATICAS
Responsable
CARRIEGOS VIEIRA , MIGUEL
Correo-e mcarv@unileon.es
mmlopc@unileon.es
Profesores/as
CARRIEGOS VIEIRA , MIGUEL
LÓPEZ CABECEIRA , MARÍA MONTSERRAT
Web http://
Descripción general "Adquisición de conocimientos sobre mecanismos computacionales ¿Qué son? ¿Cómo funcionan? Conocer perfectamente el concepto de Lenguaje Formal y de Autómata. Describir la Jerarquía de Lenguajes y traducirla a jerarquía de problemas cada uno de ellos con una clase de mecanismo computacional (autómata) adecuado para su resolución efectiva. Manejar con soltura los distintos tipos de autómatas y gramáticas. El concepto de Gramática Formal y su relación con los Lenguajes y con los Autómatas. Árboles de derivación de palabras. Explorar las posibilidades teóricas de descripción y estudio de los autómatas finitos vía sus invariantes sintácticos algebraicos. Delimitar las distintas clases de lenguajes haciendo particular énfasis en los resultados de bombeo de palabras. Relacionar los conceptos de jerarquía de gramáticas y niveles de análisis (léxico, sintáctico y semántico) haciendo énfasis en los dos primeros vía manejo de herramientas informáticas adecuadas. Estudiar el concepto de Computabilidad ¿qué problemas son resolubles vía un algoritmo? Conocer la Tesis de Turing y los límites de lo computable. Explorar otras vías de computación no clásicas (fuera de la Teoría de Turing)." "
Tribunales de Revisión
Tribunal titular
Cargo Departamento Profesor
Tribunal suplente
Cargo Departamento Profesor

Objetivos
"Adquisición de conocimientos sobre mecanismos computacionales ¿Qué son? ¿Cómo funcionan? Conocer perfectamente el concepto de Lenguaje Formal y de Autómata. Describir la Jerarquía de Lenguajes y traducirla a jerarquía de problemas cada uno de ellos con una clase de mecanismo computacional (autómata) adecuado para su resolución efectiva. Manejar con soltura los distintos tipos de autómatas y gramáticas. El concepto de Gramática Formal y su relación con los Lenguajes y con los Autómatas. Árboles de derivación de palabras. Explorar las posibilidades teóricas de descripción y estudio de los autómatas finitos vía sus invariantes sintácticos algebraicos. Delimitar las distintas clases de lenguajes haciendo particular énfasis en los resultados de bombeo de palabras. Relacionar los conceptos de jerarquía de gramáticas y niveles de análisis (léxico, sintáctico y semántico) haciendo énfasis en los dos primeros vía manejo de herramientas informáticas adecuadas. Estudiar el concepto de Computabilidad ¿qué problemas son resolubles vía un algoritmo? Conocer la Tesis de Turing y los límites de lo computable. Explorar otras vías de computación no clásicas (fuera de la Teoría de Turing)." "

Metodologías

Sin docencia

Contenidos
Bloque Tema
"I. LENGUAJES REGULARES Conjuntos, semigrupos y monoides, alfabetos y lenguajes. Lenguajes regulares. Expresiones regulares. Autómata finito. Máquinas secuenciales de estado finito. Propiedades de los lenguajes regulares. Gramáticas regulares. II. LENGUAJES INDEPENDIENTES DEL CONTEXTO Gramáticas independientes del contexto. Lenguajes independientes del contexto. Propiedades. Autómata de Pila. Laboratorio: Análisis léxico y sintáctico. III. MÁQUINAS DE TURING Y COMPUTACIÓN Máquinas de Turing. Lenguajes recursivos. Máquinas de registro ilimitado. Funciones recursivas. Resolubilidad. Computabilidad. Introducción a las redes neuronales."

Otras actividades
"

Evaluación
  descripción calificación
 
Otros comentarios y segunda convocatoria

Examen final

Fuentes de información
Acceso a la Lista de lecturas de la asignatura

Básica
"- J.E. Hopcroft, R. Motwani, J.D. Ullman. ""Introducción a la Teoría de Autómatas, Lenguajes y Computación"". Addison-Wesley, 2002. - D. Kelley. ""Teoría de Autómatas y Lenguajes Formales"". Prentice-Hall, 1998. - J. Glenn Brookshear. ""Teoría de la Computación"". Addison-Wesley. - E. Alfonseca, M. Alfonseca y R. Moriyón. ""Teoría de Autómatas y Lenguajes Formales"". Mac Graw Hill 2007" "
Complementaria
"- P. Isasi, P. Martínez, D. Borrajo. ""Lenguajes, Gramáticas y Autómatas. Un enfoque práctico"". Addison-Wesley. - G. Fernández, F. Sáez-Vacas. ""Fundamentos de Informática"". Anaya." "