TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES

GRADO EN INGENIERÍA INFORMÁTICA EN SISTEMAS DE INFORMACIÓN

1. Datos de la asignatura

(Fecha última modificación: 21-07-17 21:53)
Código
105937
Plan
ECTS
6.00
Carácter
OPTATIVA
Curso
3
Periodicidad
Segundo Semestre
Área
LENGUAJES Y SISTEMAS INFORMÁTICOS
Departamento
Informática y Automática
Plataforma Virtual

Campus Virtual de la Universidad de Salamanca

Datos del profesorado

Profesor
Hernando Silva Varela
Grupo/s
1
Departamento
Informática y Automática
Área
Lenguajes y Sistemas Informáticos
Centro
E. Politécnica Superior de Zamora
Despacho
234 y 122 del Edificio Administrativo
Horario de tutorías
-
URL Web
http://web.usal.es/hernando/
E-mail
hernando@usal.es
Teléfono
980 545 000 Ext. 3706
Profesor
María Dolores Muñoz Vicente
Grupo/s
1
Departamento
Informática y Automática
Área
Lenguajes y Sistemas Informáticos
Centro
E. Politécnica Superior de Zamora
Despacho
233-Edificio Politécnica
Horario de tutorías
-
URL Web
-
E-mail
mariado@usal.es
Teléfono
980 545 000 Ext 3635

2. Sentido de la materia en el plan de estudios

Bloque formativo al que pertenece la materia.

Formación complementaria.

Papel de la asignatura.

Esta asignatura proporciona al estudiante una formación complementaria sobre las máquinas abstractas y los problemas que éstas pueden resolver en relación, principalmente, con los lenguajes formales.

En este sentido, el conocimiento de este campo de las ciencias de la computación permite obtener fundamentos teóricos y prácticos para el estudio, diseño y/o conocimiento de analizadores sintácticos, compiladores e intérpretes de lenguajes de programación e, incluso, abordar cuestiones de procesamiento del lenguaje natural.

Perfil profesional.

La ubicación temporal de esta asignatura en el programa de estudios se establece en los cursos superiores del Grado y demanda del estudiante conocimiento de los lenguajes de programación, el manejo de sistemas operativos y una base sólida de conocimientos matemáticos básicos. Es recomendable poseer también una buena capacidad de análisis, aprendizaje y trabajo individual y en equipo.

 

La asignatura aportará al estudiante nuevos conocimientos para comprender el funcionamiento de los analizadores sintácticos, intérpretes y compiladores de los lenguajes de programación. En un contexto más amplio, sienta las bases para abordar aspectos del procesamiento del lenguaje natural tales como la clasificación de patrones y/o el reconocimiento automático del habla.

 

La asignatura aportará también al estudiante nuevos conocimientos, competencias sociales y emocionales, capacidades estratégicas, organizativas y de planificación. Todo esto contribuye a formarle como un profesional multifuncional con una buena actitud ante los cambios y con capacidad de autoaprendizaje.

3. Recomendaciones previas

Es recomendable una buena actitud de trabajo del estudiante y ser capaz de manejarse de manera cómoda tanto en sistemas operativos Windows como linux. Además, se sugiere un buen manejo de aspectos elementales de la matemática en el ámbito del álgebra y la teoría de conjuntos. Es necesario disponer también de conocimientos de programación.

4. Objetivo de la asignatura

-     Introducir al alumno en el conocimiento de los autómatas como modelos y herramientas para el procesamiento de lenguajes.

-     Sentar las bases para el estudio, conocimiento y diseño de analizadores sintácticos, intérpretes y compiladores.

-     Dotar al estudiante de herramientas para abordar el estudio de sistemas para el procesamiento del lenguaje natural.

-     Dar al alumno la capacidad de relacionar conceptos, conocimientos e información de materias y asignaturas afines.

-     Aplicar conocimientos adquiridos previamente de una cantidad de fuentes de carácter muy diverso hacia un área de las ciencias de la computación.

-     Adquirir capacidad de organización, planificación del trabajo, análisis, crítica, síntesis y trabajo en individual y en equipo.

-     Desarrollar capacidades de comunicación oral y escrita de conocimientos, ideas, procedimientos, experiencias, resultados.

-              Fomentar el trabajo autónomo, el análisis, la autocrítica y la toma de decisiones.

5. Contenidos

Teoría.

El programa de la asignatura comprende tanto aspectos teóricos como prácticos

 

PROGRAMA DE TEORÍA

 

Bloque I: Introducción y conceptos preliminares.

 

Tema 1: Introducción a la TALF.

Tema 2: Alfabetos, cadenas y lenguajes.

 

Bloque II: Autómatas Finitos.

 

Tema 3: Autómatas Finitos Deterministas (AFDs).

Tema 4: Autómatas Finitos No Deterministas (AFNs).

Tema 5: Equivalencia entre AFDs y AFNs.

Tema 6: Autómatas Finitos con transiciones nulas (AFN-λ).

 

Bloque III: Expresiones y lenguajes regulares.

 

Tema 7: Expresiones regulares.

Tema 8: Propiedades de los lenguajes regulares.

 

Bloque III: Gramáticas Independientes del Contexto y Autómatas de Pila.

 

Tema 9: Gramáticas Independientes del Contexto (GIC).

Tema 10: Aplicaciones de las Gramáticas Independientes del Contexto.

Tema 11: Ambigüedad en las GIC y los LIC.

Tema 12: Autómatas de Pila (AP).

Tema 13: Propiedades de los LIC.

Práctica.

Modelado y simulación de Autómatas Finitos Deterministas (AFDs).

 

Modelado y simulación de Autómatas Finitos No Deterministas (AFN).

 

Transformación de un AFN en un AFD.

 

Minimización de estados en un AFD.

 

Modelado y simulación de autómatas finitos no deterministas con transiciones λ.

 

Transformación de una expresión regular en un AFN-λ.

 

Introducción a YACC.

 

Análisis sintáctico

 

Autómatas de pila.

 

Simulación de máquinas de Turing.

6. Competencias a adquirir

Específicas.

CO02. Capacidad para conocer los fundamentos teóricos de los lenguajes de programación y las técnicas de procesamiento léxico, sintáctico y semántico asociadas, y saber aplicarlas para la creación, diseño y procesamiento de lenguajes.

Transversales.

CT01. Capacidad de organización, gestión y planificación del trabajo.

CT02. Capacidad de análisis, crítica y síntesis.

CT03. Capacidad para relacionar y gestionar diversas informaciones e integrar conocimientos e ideas.

CT05. Capacidad de toma de decisiones.

CT09. Capacidad de comunicación, tanto oral como escrita, de conocimientos, ideas, procedimientos, y resultados, en lengua nativa.

CT10. Capacidad de integración en grupos de trabajo unidisciplinares o multidisciplinares.

CT11. Aprendizaje autónomo.

7. Metodologías

La metodología docente de la asignatura tiene como eje principal, más no único, las actividades presenciales. A este apartado se añaden otros para la resolución de problemas, preparar exposición de trabajos, problemas para entregar, tutorías y espacio virtual.

 

CLASE MAGISTRAL: Actividad presencial para la exposición de ideas, conceptos y conocimientos, por parte del profesor, así como para el seguimiento de los alumnos y coordinación general de la asignatura.

 

RESOLUCIÓN DE PROBLEMAS: Actividad presencial para la solución, por parte del profesor, de problemas de carácter teórico y/o práctico relacionados con los temas tratados en la asignatura. También se plantearán problemas para ser resueltos por los alumnos con la ayuda y colaboración del Profesor y resto de los estudiantes.

 

EXPOSICIÓN DE TRABAJOS: Actividad presencial para que los alumnos expongan en el aula y ante sus compañeros, por medios audiovisuales, trabajos estrechamente relacionados con la asignatura que se hayan asignado y preparado previamente con tiempo suficiente.

 

PROBLEMAS FUERA DE CLASE: Actividad no presencial donde los alumnos resuelven problemas planteados por el profesor para que entreguen resueltos todos o parte de ellos según se haya comunicado previamente a aquéllos.

 

PRÁCTICAS: Actividad presencial donde se resuelven en ordenador problemas planteados por el profesor. La solución de estos problemas requerirá principalmente programación en ordenador.

 

TUTORÍAS: Actividad presencial de atención personalizada a uno o varios alumnos para que el profesor atienda los requerimientos de éstos en la resolución de dudas, ayuda en la solución de problemas, guía en el desarrollo de trabajos y asesoría en la preparación de exámenes.

 

ESPACIO VIRTUAL: El espacio virtual es un sitio de encuentro a distancia para ayudar a coordinar la asignatura, en general, y comunicarse con los alumnos. Es también el lugar donde se pueden desarrollar en menor medida alguna de las actividades que se realizan en las tutorías.

8. Previsión de Técnicas (Estrategias) Docentes

9. Recursos

Libros de consulta para el alumno.

HOPCROFT, JOHN E. y ULLMAN, JEFFREY D. (2002), “Introducción a la teoría de autómatas, lenguajes y computación”, 2ª edición, Addison- Wesley.

 

BROOKSHEAR, J. G., (1993), “Teoría de la Computación: Lenguajes Formales, Autómatas y Complejidad”, Addison-Wesley Longman.

 

AHO, ALFRED V., SETHI, RAVI y ULLMAN, JEFFREY D. (1986), “Compilers: Principles, Techniques and Tools”, Addison-Wesley.

 

ALFRED V. y ULLMAN, JEFFREY D. (1977), “Principles of Compiler Design”, Pearson Addison-Wesley.

 

Otras referencias bibliográficas, electrónicas o cualquier otro tipo de recurso.

10. Evaluación

Consideraciones generales.

Se llevará a cabo una evaluación continua del estudiante teniendo en cuenta:

 

  1. Asistencia y participación activa de éste en la clase (10%).
  2. Desarrollo y/o exposición de trabajos teóricos y prácticos (30%).
  3. Desarrollo de prácticas en aula de ordenadores (40%).
  4. Exámenes optativos con preguntas y/o problemas (20%).

 

Cada una de las cuatro partes anteriores se evalúa en una escala del 0 al 10 y la nota final se obtiene de la suma de cada una de las cuatro partes ponderada por su peso porcentual. Es decir:

 

                  NOTA FINAL = 0,1 a + 0,3 b + 0,4 c + 0,2 d

 

Se realizarán pruebas escritas de recuperación para los alumnos que no superen la asignatura mediante evaluación continua. La calificación obtenida en dichas pruebas no podrá computar más de un 45% de la calificación global de la asignatura.

Criterios de evaluación.

Se utilizará el sistema de calificaciones vigente (RD 1125/2003) artículo 5º. Los resultados obtenidos por el alumno en cada una de las materias del plan de estudios se calificarán en función de la siguiente escala numérica de 0 a 10, con expresión de un decimal, a la que podrá añadirse su correspondiente calificación cualitativa:

 

 0 - 4,9: Suspenso (SS)

5,0 - 6,9: Aprobado (AP)

7,0 - 8,9: Notable (NT)

9,0 - 10: Sobresaliente (SB).

La mención de Matrícula de Honor podrá ser otorgada a alumnos que hayan obtenido una calificación igual o superior a 9,0. Su número no podrá exceder del 5% de los alumnos matriculados en una asignatura en el correspondiente curso académico, salvo que el número de alumnos matriculados sea inferior a 20, en cuyo caso se podrá conceder una sola Matrícula de Honor.

Se tendrá en cuenta en todos los casos el Reglamento de Evaluación de la Universidad de Salamanca.

Instrumentos de evaluación.

•       Seguimiento de la evolución en clase del alumno, asistencia, participación en clase, prácticas y trabajos realizados (incluyendo defensa de los mismos).

•             Prácticas y exámenes o pruebas teóricas.

Recomendaciones para la evaluación.

La asistencia a clase y la participación activa del alumno, unido al trabajo continuo, permiten superar sin dificultad la asignatura.

Recomendaciones para la recuperación.

Informarse ante el profesor sobre cuales apartados de la evaluación son susceptibles de recuperar para subsanarlos con el fin de aprobar la asignatura.

11. Organización docente semanal