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

Presentación

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.

Competencias

A continuación se enumeran las competencias que adquirirás al cursar esta asignatura:

Competencias básicas

  • CB1: Que los estudiantes hayan demostrado poseer y comprender conocimientos en un área de estudio que parte de la base de la educación secundaria general, y se suele encontrar a un nivel que, si bien se apoya en libros de texto avanzados, incluye también algunos aspectos que implican conocimientos procedentes de la vanguardia de su campo de estudio.
  • CB2: Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio.
  • CB3: Que los estudiantes tengan la capacidad de reunir e interpretar datos relevantes (normalmente dentro de su área de estudio) para emitir juicios que incluyan una reflexión sobre temas relevantes de índole social, científica o ética.
  • CB4: Que los estudiantes puedan transmitir información, ideas, problemas y soluciones a un público tanto especializado como no especializado.
  • CB5: Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía.

Competencias generales

  • CG8: Conocimiento de las materias básicas y tecnologías, que capaciten para el aprendizaje y desarrollo de nuevos métodos y tecnologías, así como las que les doten de una gran versatilidad para adaptarse a nuevas situaciones.
  • CG9: Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesión de Ingeniero Técnico en Informática.

Competencias específicas

  • CC02: 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.

Competencias transversales

  • CT1: Capacidad de innovación y flexibilidad en entornos nuevos de aprendizaje como es la enseñanza on-line.
  • CT2: Conocer, y utilizar con habilidad, los mecanismos básicos de uso de comunicación bidireccional entre profesores y alumnos, foros, chats, etc.
  • CT3: Utilizar las herramientas para presentar, producir y comprender la información que les permita transformarla en conocimiento.


Contenidos

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


Metodología

Metodología

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:

  • Trabajos y Lecturas. Se trata de actividades de diferentes tipos: reflexión, análisis de casos, prácticas, etc. Además de análisis de textos relacionados con diferentes temas de la asignatura.
  • Participación en eventos. Son eventos programados todas las semanas del cuatrimestre: sesiones presenciales virtuales, foros de debate, test.
  • Laboratorios. Actividad práctica que se realiza en tiempo real e interactuando con otros alumnos. En el laboratorio los estudiantes tendrán que desarrollar los ejercicios propuestos en un entorno de simulación online. Los estudiantes contarán en todo momento con el apoyo de un tutor de laboratorio, que ayudará al
    alumno a desarrollar su actividad. El tutor de laboratorio podrá asignar grupos de alumnos para que, de forma
    colaborativa, alcancen los resultados solicitados. Este tipo de actividad posee un peso considerable en la
    evaluación continua del alumno, por lo que, a pesar de no ser obligatoria su realización, se recomienda firmemente la participación en los mismos.

En la programación semanal puedes consultar cuáles son las actividades concretas que tienes que realizar en esta asignatura.

Descarga el pdf de la programación

Estas actividades formativas prácticas se completan, por supuesto, con estas otras:

  • Estudio personal
  • Tutorías. Las tutorías se pueden articular a través de diversas herramientas y medios. Durante el desarrollo de la asignatura, el profesor programa tutorías en días concretos para la resolución de dudas de índole estrictamente académico a través de las denominadas “sesiones de consultas”. Como complemento de estas sesiones se dispone también del foro “Pregúntale al profesor de la asignatura” a través del cual se articulan algunas preguntas de alumnos y las correspondientes respuestas en el que se tratan aspectos generales de la asignatura. Por la propia naturaleza de los medios de comunicación empleados, no existen horarios a los que deba ajustarse el alumno.
  • Examen final presencial

Las horas de dedicación a cada actividad se detallan en la siguiente tabla:

ACTIVIDADES FORMATIVAS 
HORAS
% PRESENCIAL
Sesiones presenciales virtuales
15
100%
Lecciones magistrales
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 presencial
2
100%
Total
150

 



Puedes personalizar tu plan de trabajo seleccionando aquel tipo de actividad formativa que se ajuste mejor a tu perfil. El profesor-tutor te ayudará y aconsejará en el proceso de elaboración de tu plan de trabajo. Y siempre estará disponible para orientarte durante el curso.

Recomendaciones técnicas

Metodología

Para la correcta participación de los alumnos en las diferentes actividades propuestas en la asignatura se recomienda disponer de un ordenador con las siguientes especificaciones mínimas recomendadas:

  • 4 GB de RAM
  • Conexión a Internet superior a 6 Mbit/s
  • Cámara web
  • Micrófono
  • Altavoces o auriculares
  • Sistema operativo Windows o Mac OS (algunas actividades pueden presentar dificultades sobre Linux. En esta circunstancia se recomienda consultar con el profesor de la asignatura)
  • Acceso de administrador al sistema (es necesario la instalación de programas, emuladores, compiladores…)
  • Navegador web Netscape, Chrome, Safari o Firefox actualizado (versiones no actualizadas pueden presentar problemas funcionales y/o de seguridad)

Bibliografía

Bibliografía básica

La bibliografía básica es imprescindible para el estudio de la asignatura. Cuando se indica que no está disponible en el aula virtual, tendrás que obtenerla por otros medios: librería UNIR, biblioteca… 

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:

  • Hopcroft, J.E., Motwani, R. y Ullman, J.D. (2008). Introducción a la teoría de autómatas, lenguajes y computación (3ª ed.).
    España: Addison-Wesley.
    ISBN: 8478290567

 

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.

Gribkof, E. (2013). Applications of Deterministic Finite Automata. UC Davis.

evaluación

Evaluación y calificación

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:

calificación

El examen se realiza al final del cuatrimestre y es de carácter PRESENCIAL y OBLIGATORIO. Supone el 60% de la calificación final (6 puntos sobre 10) y para que la nota obtenida en este examen se sume a la nota final, es obligatorio APROBARLO (es decir, obtener 3 puntos de los 6 totales del examen).

La evaluación continua supone el 40% de la calificación final (es decir, 4 puntos de los 10 máximos). 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 es de 6 puntos. Así, puedes hacer las que prefieras hasta conseguir un máximo de 4 puntos (que es la calificación máxima que se puede obtener en la evaluación continua). En la programación semanal de la asignatura, se detalla la calificación máxima de cada actividad o evento concreto puntuables.

SISTEMA DE EVALUACIÓN 
PONDERACIÓN MIN. 
PONDERACIÓN MÁX. 
Prueba de evaluación final presencial
60%
60%
Evaluación de prácticas de laboratorios virtuales
0%
40%
Resolución de trabajos, proyectos y casos
0%
40%
Participación en foros y otros medios participativos
0%
40%

 

Ten en cuenta…
Si quieres presentarte sólo al examen final, tendrás que obtener una calificación de 5 puntos sobre 6 para aprobar la asignatura.

Profesorado

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.

Orientaciones para el estudio

Orientación para el estudio

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:

  1. Desde el Campus virtual podrás acceder al aula virtual de cada asignatura en la que estés matriculado y, además, al aula virtual de Lo que necesitas saber antes de empezar. Aquí podrás consultar la documentación disponible sobre cómo se utilizan las herramientas del aula virtual y sobre cómo se organiza una asignatura en la UNIR y también podrás organizar tu plan de trabajo personal con tu profesor-tutor.
  2. Observa la programación semanal. Allí te indicamos qué parte del temario debes trabajar cada semana.
  3. Ya sabes qué trabajo tienes que hacer durante la semana. Accede ahora a la sección Temas del aula virtual. Allí encontrarás el material teórico y práctico del tema correspondiente a esa semana.
  4. Comienza con la lectura de las Ideas clave del tema. Este resumen te ayudará a hacerte una idea del contenido más importante del tema y de cuáles son los aspectos fundamentales en los que te tendrás que fijar al estudiar el material básico. Lee siempre el primer apartado, ¿Cómo estudiar este tema?, porque allí te especificamos qué material tienes que estudiar. Consulta, además, las secciones del tema que contienen material complementario (Lo + recomendado y + Información).
  5. Dedica tiempo al trabajo práctico (sección Actividades y Test). En la programación semanal te detallamos cuáles son las actividades correspondientes a cada semana y qué calificación máxima puedes obtener con cada una de ellas.
  6. Te recomendamos que participes en los eventos del curso (sesiones presenciales virtuales, foros de debate…). Para conocer la fecha concreta de celebración de los eventos debes consultar las herramientas de comunicación del aula vitual. Tu profesor y tu profesor-tutor te informarán de las novedades de la asignatura.
En el aula virtual de Lo que necesitas saber antes de empezar encontrarás siempre disponible la documentación donde te explicamos cómo se estructuran los temas y qué podrás encontrar en cada una de sus secciones: Ideas clave, Lo + recomendado, + Información, Actividades y Test.

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…

  • Sea cual sea tu plan de estudio, accede periódicamente al aula virtual, ya que de esta forma estarás al día de las novedades del curso y en contacto con tu profesor y con tu profesor tutor.
  • Recuerda que no estás solo: consulta todas tus dudas con tu profesor-tutor utilizando el correo electrónico. Si asistes a las sesiones presenciales virtuales también podrás preguntar al profesor sobre el contenido del tema. Además, siempre puedes consultar tus dudas sobre el temario en los foros que encontrarás en cada asignatura (Pregúntale al profesor).
  • ¡Participa! Siempre que te sea posible accede a los foros de debate y asiste a las sesiones presenciales virtuales. El intercambio de opiniones, materiales e ideas nos enriquece a todos.
  • Y ¡recuerda!, estás estudiando con metodología online: tu esfuerzo y constancia son imprescindibles para conseguir buenos resultados. ¡No dejes todo para el último día!