Última revisión realizada: 23/05/2022
Denominación de la asignatura |
Teoría de Autómatas y Lenguajes Formales |
Grado al que pertenece |
Grado en Ingeniería Informática |
Créditos ECTS |
6 |
Curso y cuatrimestre en el que se imparte |
Primer cuatrimestre |
Materia |
Computación |
Carácter de la asignatura | Optativa |
En la asignatura de Teoría de Autómatas y Lenguajes Formales se busca que el alumno se inicie en los conceptos básicos de la informática teórica, es decir, se van a trabajar los lenguajes y gramáticas formales y los distintos autómatas asociados a ellas. En concreto, se van a estudiar las gramáticas de tipo 1, 2 y 3 según la jerarquía de Chomsky.
Es una asignatura de marcado carácter teórico, pero fundamental en la formación de un ingeniero informático, ya que el estudio de estos conceptos no sólo sirve de base para poder estudiar a fondo las máquinas de Turing (que pueden resolver el mismo tipo de problemas que cualquier computador), sino que tienen aplicaciones evidentes en el campo de los traductores de lenguaje, en los que resulta necesario saber si una cadena dada pertenece a un lenguaje determinado o no.
En este curso no sólo se van a abordar las definiciones básicas y resultados teóricos más relevantes. Con el fin de que el alumno se consiga desenvolver bien con estos conceptos, se van a realizar una serie de actividades teóricas. En concreto, se consideran de especial importancia el reconocimiento de lenguajes mediante la programación de autómatas. También se explica la aplicación de estos conceptos a la resolución de algunos problemas prácticos.
A continuación se enumeran las competencias que adquirirás al cursar esta asignatura:
Competencias básicas
Competencias generales
Competencias específicas
Competencias transversales
Tema 1. Introducción a la teoría de autómatas
¿Por qué estudiar teoría de autómatas?
Introducción a las demostraciones formales
Otras formas de demostración
Inducción matemática
Alfabetos, cadenas y lenguajes
Tema 2. Autómatas finitos deterministas
Introducción a los autómatas finitos
Autómatas finitos deterministas
Tema 3. Autómatas finitos deterministas
Autómatas finitos no deterministas
Equivalencia entre AFD y AFN
Autómatas finitos con transiciones ϵ
Tema 4. Lenguajes y expresiones regulares
Lenguajes y expresiones regulares
Autómatas finitos y expresiones regulares
Tema 5. Lenguajes y expresiones regulares
Conversión de expresiones regulares en autómatas
Aplicaciones de las expresiones regulares
Álgebra de las expresiones regulares
Tema 6. Lema de bombeo y clausura de los lenguajes regulares
Lema de bombeo
Propiedades de clausura de los lenguajes regulares
Tema 7. Equivalencia y minimización de autómatas
Equivalencia de AF
Minimización de AF
Tema 8. Gramáticas independientes de contexto
Gramáticas independientes de contexto
Árboles de derivación
Tema 9. Aplicación de las GIC. Ambigüedades en los lenguajes
Aplicaciones de las GIC
Ambigüedad en las gramáticas y lenguajes
Tema 10. Autómatas a pila
Definición de los autómatas a pila
Lenguajes aceptados por un autómata a pila
Tema 11. Autómatas a pila y GIC
Equivalencia entre autómatas a pila y GIC
Autómata a pila determinista
Tema 12. Formas normales y lema de bombeo de las GIC
Formas normales de las GIC
Lema de bombeo
Tema 13. Propiedades de los LIC
Propiedades de clausura de los lenguajes
Propiedades de decisión de los LIC
Las actividades formativas de la asignatura se han elaborado con el objetivo de adaptar el proceso de aprendizaje a las diferentes capacidades, necesidades e intereses de los alumnos.
Las actividades formativas de esta asignatura son las siguientes:
En la programación semanal puedes consultar cuáles son las actividades concretas que tienes que realizar en esta asignatura.
Estas actividades formativas prácticas se completan, por supuesto, con estas otras:
Las horas de dedicación a cada actividad se detallan en la siguiente tabla:
ACTIVIDADES FORMATIVAS |
HORAS |
% PRESENCIAL |
Sesiones presenciales virtuales | 15 |
100% |
Recursos didácticos audiovisuales | 6 |
0 |
Estudio del material básico | 50 |
0 |
Lectura del material complementario | 25 |
0 |
Trabajos, casos prácticos, test | 17 |
0 |
Prácticas de laboratorios virtuales | 12 |
16,7% |
Tutorías | 16 |
30% |
Trabajo colaborativo | 7 |
0 |
Realización de examen final | 2 |
100% |
Total | 150 |
Bibliografía básica
Los textos necesarios para el estudio de la asignatura han sido elaborados por UNIR y están disponibles en formato digital para consulta, descarga e impresión en el aula virtual.
Además, en algunos temas deberás estudiar el siguiente manual de la asignatura:
Bibliografía complementaria
Alfonseca, E., Alfonseca, M. y Moriyón, R. (2007). Teoría de Autómatas y Lenguajes Formales (pp. 1-5). Madrid: Mc Graw Hill.
Gaudioso, E., García , T. (2017). Introducción a la Teoría de Autómatas, Gramáticas y Lenguajes (Manuales). Madrid: Editorial Universitaria Ramón Areces.
Giró, J., Vázquez, J., Meloni, B. y Constable, L. (2015). Lenguajes formales y teoría de autómatas. Madrid: Alfaomega.
Gribkof, E. (2013). Applications of Deterministic Finite Automata. UC Davis.
El sistema de calificación se basa en la siguiente escala numérica:
0 - 4, 9 |
Suspenso |
(SS) |
5,0 - 6,9 |
Aprobado |
(AP) |
7,0 - 8,9 |
Notable |
(NT) |
9,0 - 10 |
Sobresaliente |
(SB) |
La calificación se compone de dos partes principales:
El examen se realiza al final del cuatrimestre y es de carácter PRESENCIAL U ONLINE y OBLIGATORIO. Supone el 60% de la calificación final y para que la nota obtenida en este examen se sume a la nota final, es obligatorio APROBARLO.
La evaluación continua supone el 40% de la calificación final. Este 40% de la nota final se compone de las calificaciones obtenidas en las diferentes actividades formativas llevadas a cabo durante el cuatrimestre.
Ten en cuenta que la suma de las puntuaciones de las actividades de la evaluación continua permite que realices las que prefieras hasta conseguir el máximo puntuable mencionado en la programación semanal. En ella se detalla la calificación máxima de cada actividad o evento concreto puntuables.
El sistema de evaluación de la asignatura es el siguiente:
SISTEMA DE EVALUACIÓN |
PONDERACIÓN MIN. |
PONDERACIÓN MÁX. |
Prueba de evaluación final | 60% |
60% |
Evaluación de prácticas de laboratorios virtuales | 0% |
40% |
Resolución de trabajos, proyectos y casos | 0% |
40% |
Test de autoevaluación | 0% |
20% |
Participación en foros y otros medios participativos | 0% |
40% |
Juan Antonio Sicilia Montalvo
Formación: Doctor en Ingeniería por la Universidad de Zaragoza. Ingeniero informático por la Universidad de Zaragoza.
Experiencia: Profesor en la Escuela de Ingeniería y en la Facultad de Empresa y Comunicación de la Universidad Internacional de La Rioja desde 2014. Autor de múltiples artículos científicos, ha participado en diversos proyectos de investigación y en congresos nacionales e internacionales.
Líneas de investigación: Optimización combinatoria, investigación operativa, sistemas decisionales, algoritmos matemáticos y modelos de planificación de transporte y logística.
Obviamente, al tratarse de formación on-line puedes organizar tu tiempo de estudio como desees, siempre y cuando vayas cumpliendo las fechas de entrega de actividades, trabajos y exámenes. Nosotros, para ayudarte, te proponemos los siguientes pasos:
Recuerda que en el aula virtual de Lo que necesitas saber antes de empezar puedes consultar el funcionamiento de las distintas herramientas del aula virtual: Correo, Foro, Sesiones presenciales virtuales, Envío de actividades, etc.
Ten en cuenta estos consejos…
|