NO EXISTEN CAMBIOS
The subject guide has been updated with the changes mentioned here
| SUBJECT NAME |
| SUBJECT NAME |
FUNDAMENTOS DE AUTÓMATAS, GRAMÁTICAS Y LENGUAJES |
| CODE |
| CODE |
71031085 |
| SESSION |
| SESSION |
2026/2027 |
| DEPARTMENT |
| DEPARTMENT |
INTELIGENCIA ARTIFICIAL
|
| DEGREE IN WHICH IT IS OFFERED |
| DEGREE IN WHICH IT IS OFFERED |
|
|
GRADO EN INGENIERÍA EN INTELIGENCIA ARTIFICIAL
|
| COURSE |
| COURSE |
PRIMER
COURSE
|
| PERIOD |
SEMESTER 2
|
| TYPE |
OBLIGATORIAS |
| CREDITS NUMBER |
| CREDITS NUMBER |
3 |
| HOURS |
| HOURS |
75 |
| LANGUAGES AVAILABLE |
| LANGUAGES AVAILABLE |
CASTELLANO |
La asignatura “Fundamentos de Autómatas, Gramáticas y Lenguajes” tiene como objetivo introducir los conceptos fundamentales de las máquinas de estados finitos que se utilizan como reconocedores de lenguajes. En cuanto a reconocedores, los autómatas constituyen la base para la construcción de compiladores, y para el estudio de la computabilidad, esto es, qué es capaz de computar una máquina y con qué complejidad.
La presente guía contiene información de carácter general sobre la asignatura, su ubicación dentro de la titulación, conocimientos previos recomendables y resultados esperados de aprendizaje.
Esta asignatura de 3 créditos ECTS, tiene carácter obligatorio y se imparte en el segundo cuatrimestre del primer curso. Es parte de la materia de Lenguajes de Programación. El conocimiento de sus contenidos es necesario para cursar las asignaturas de Teoría de los Lenguajes de Programación y de Lenguajes de Programación y Procesadores.
Esta asignatura se sitúa, por tanto, en el nivel básico dentro del plan de formación de este grado y desarrolla las competencias relacionadas con las capacidades 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; saber aplicar las citadas técnicas para la creación, diseño y procesamiento de lenguajes.
Todo ello contribuye al perfil profesional del ingeniero en Inteligencia Artificial proporcionando los fundamentos teóricos para el desarrollo de compiladores, intérpretes y procesadores de lenguaje, así como de sistemas inteligentes en general, capacitándole para comprender y aplicar los mecanismos formales que subyacen al diseño y análisis de lenguajes de programación.
Al tratarse de una asignatura básica de primer curso, no se requiere ningún requisito previo más allá de los conocimientos que un alumno debe tener en este nivel de enseñanza. Para seguir con más facilidad la asignatura será de utilidad recordar los conocimientos básicos sobre teoría básica de conjuntos.
Las consultas sobre los contenidos o sobre el funcionamiento de la asignatura se plantearán preferentemente en el curso virtual, utilizando los foros públicos.
Así mismo, para consultas más individualizadas, existe la posibilidad de contactar con el equipo docente directamente utilizando el correo electrónio. También es posible contactar por teléfono o por videollamada acordando una cita a través del correo electrónico.
Los datos de contacto del equipo docente son los siguientes:
Elena Gaudioso Vázquez; elena@dia.uned.es
Horario de guardias: lunes y martes, de 10 a 12 h.
Tfno: 91 398 84 50; Despacho 3.10; E.T.S.I. Informática. UNED
Félix Hernández del Olmo; felixh@dia.uned.es
Horario de guardias: miércoles y jueves de 10:00 a 12:00
Tfno. 91 398 83 45; Despacho 3.6; E.T.S.I. Informática. UNED
La E.T.S.I. Informática de la UNED está situada en la Ciudad Universitaria de Madrid. La dirección postal es:
C/ Juan del Rosal, 16, 28040. Madrid
En el enlace que aparece a continuación se muestran los centros asociados y extensiones en las que se imparten tutorías de la asignatura. Estas pueden ser:
Consultar horarios de tutorización de la asignatura 71031085
Horarios de
FUNDAMENTOS DE AUTÓMATAS, GRAMÁTICAS Y LENGUAJES
Loading, this may take a while
Cargando...
Ver sección de Resultados de Aprendizaje
El estudio de esta asignatura permite avanzar en la adquisición de los siguientes resultados de aprendizaje:
RA06 - Al finalizar el aprendizaje, el o la estudiante será capaz de analizar las necesidades en algorítmica, complejidad computacional, programación, sistemas operativos, bases de datos, estructura, interconexión de sistemas informáticos necesarios para la resolución de problemas de ciencias e ingeniería, de acuerdo con los principios de calidad, fiabilidad y seguridad necesarios.
RA13 - Al finalizar el aprendizaje, el o la estudiante será capaz de demostrar conocimientos y técnicas básicas de los diferentes enfoques de la inteligencia artificial y su integración como profesionales de inteligencia artificial en equipos multidisciplinares.
Introducción a los autómatas, gramáticas y lenguajes
Este primer tema sitúa al estudiante en el marco general de la asignatura, presentando los tres grandes objetos de estudio: los autómatas, las gramáticas y los lenguajes formales. Se introduce la noción de lenguaje formal como conjunto de cadenas sobre un alfabeto, así como las operaciones básicas sobre lenguajes y las distintas formas de describirlos y reconocerlos. Se presentan también los mecanismos generativos —las gramáticas— y los mecanismos reconocedores —los autómatas— como dos perspectivas complementarias para caracterizar un mismo objeto matemático. El tema incluye asimismo una primera aproximación a la jerarquía de Chomsky, que establece una clasificación de los lenguajes formales en función de la complejidad de las gramáticas y los autómatas que los definen, y que servirá de hilo conductor a lo largo del resto de la asignatura.
Por tanto, los contenidos de mayor dificultad de este tema residen en la asimilación de conceptos nuevos y abstractos, como la distinción entre lenguaje formal y conjunto de cadenas aceptadas por un autómata, o los mecanismos de derivación en gramáticas formales.
Lenguajes regulares
Este tema aborda la familia de lenguajes formales más sencilla dentro de la jerarquía de Chomsky: los lenguajes regulares. Se estudian sus tres mecanismos de descripción equivalentes —las expresiones regulares, las gramáticas regulares y los autómatas finitos, tanto deterministas como no deterministas— y se establecen las relaciones de equivalencia entre ellos. El tema concluye con una introducción a las propiedades y al poder expresivo y las limitaciones de los lenguajes regulares, sentando así las bases para comprender la necesidad de mecanismos más potentes.
Los contenidos de mayor dificultad de este tema residen en la demostración y comprensión de las equivalencias entre los distintos mecanismos de descripción —expresiones regulares, gramáticas regulares y autómatas finitos deterministas y no deterministas—, así como en identificar qué lenguajes no pueden ser reconocidos por autómatas finitos y, por tanto, escapan al poder expresivo de los lenguajes regulares.
Lenguajes independientes del contexto
Este tema da un paso adelante en la jerarquía de Chomsky, presentando los lenguajes independientes del contexto como una familia más amplia y expresiva que la de los lenguajes regulares. Se estudian las gramáticas independientes del contexto y sus formas normales —en particular las formas normales de Chomsky—, así como los autómatas a pila como mecanismo reconocedor equivalente. Por último, se introducen las aplicaciones prácticas de estos lenguajes así como sus limitaciones.
Los contenidos de mayor dificultad de este tema residen en la comprensión del funcionamiento de los autómatas a pila y su equivalencia con las gramáticas independientes del contexto, así como en identificar qué lenguajes quedan fuera del poder expresivo de esta familia y requieren mecanismos de reconocimiento más potentes.
Introducción a los lenguajes recursivamente enumerables
Este tema cierra el recorrido por la jerarquía de Chomsky presentando el nivel más general: los lenguajes recursivamente enumerables y su relación con las máquinas de Turing. Se introduce la máquina de Turing como modelo universal de cómputo. Se aborda la definición de lenguaje decidible, y se presenta un caso clásico de indecidibilidad, el problema de la parada. El tema ofrece así una primera toma de contacto con los límites intrínsecos de la computación, proporcionando una perspectiva teórica que complementa y enriquece la formación del estudiante en inteligencia artificial.
Los contenidos de mayor dificultad de este tema residen en la asimilación de los conceptos de decidibilidad e indecidibilidad y sus implicaciones.
Las diferentes asignaturas que integran este grado, se impartirán todas ellas conforme a la metodología no presencial que caracteriza a la UNED, en la cual prima el autoprendizaje del alumno, asistido por el profesor mediante diversos sistemas de comunicación docente-discente mayoritariamente asíncronos y por las tutorías que pueden ser presenciales, impartidas en los Centros Asociados, o semipresenciales permitiendo la conexión del alumnado a las sesiones con independencia de su localización geográfica. Además, la docencia se imparte con apoyo de una plataforma virtual interactiva en la que se combinan distintos recursos, los medios impresos y los audiovisuales y virtuales. Más en concreto, la plataforma virtual contendrá: contenidos, foros de discusión, glosario de términos, tareas y enlaces de interés.
ONSITE TEST
|
| Type of exam |
| Type of exam |
Examen tipo test |
| Quiz questions |
| Quiz questions |
10 |
| Duration of the exam |
| Duration of the exam |
120 (minutes) |
| Material allowed in the exam |
| Material allowed in the exam |
Ninguno |
| Assessment criteria |
| Assessment criteria |
El examen es de tipo test con 10 preguntas con cuatro opciones cada una. Únicamente habrá una opción verdadera. Las preguntas mal contestadas restarán puntos y las preguntas en blanco no penalizarán. |
| % Concerning the final grade |
| % Concerning the final grade |
90 |
| Minimum grade (not including continuas assessment) |
| Minimum grade (not including continuas assessment) |
0 |
| Maximum grade (not including continuas assessment) |
| Maximum grade (not including continuas assessment) |
9 |
| Minimum grade (including continuas assessment) |
| Minimum grade (including continuas assessment) |
|
| Coments |
| Coments |
|
CONTINUOUS ASSESSMENT TEST (PEC)
|
| PEC? |
| PEC? |
No |
| Description |
| Description |
No está previsto la realización de PEC en esta asignatura. La prueba de evaluación asíncrona consistirá en una práctica experimental (de laboratorio) no presencial asíncrona (ver definición de la práctica) |
| Assessment criteria |
| Assessment criteria |
|
| Weighting of the PEC in the final grade |
| Weighting of the PEC in the final grade |
|
| Approximate submission date |
| Approximate submission date |
|
| Coments |
| Coments |
|
OTHER GRADEABLE ACTIVITIES
|
| Are there other evaluable activities? |
| Are there other evaluable activities? |
Si |
| Description |
| Description |
En esta asignatura se plantea una práctica de laboratorio no presencial asíncrona que consistirá en una serie de ejercicios o problemas a realizar por el alumno utilizando el software que indique el equipo docente. |
| Assessment criteria |
| Assessment criteria |
Los ejercicios se evaluarán de acuerdo a las soluciones y criterios de evaluación proprocionados por el equipo docente y que se publicarán en el curso virtual. IMPORTANTE: Hay que obtener una nota mínima de 5 puntos en la prueba presencial para que se tome en consideración la calificación de la práctica. |
| Weighting in the final grade |
| Weighting in the final grade |
10% |
| Approximate submission date |
| Approximate submission date |
Alrededor de principios de mayo (se anunciará en el curso virtual) |
| Coments |
| Coments |
Debido al planteamiento de evaluación continua definido en el Espacio Europeo de Educación Superior en el que se enmarca la asignatura, el alumno debe tener en cuenta que sólo se corregirán la práctica durante el cuatrimestre en el que se imparte la asignatura. Para la convocatoria de septiembre, se mantendrá la nota obtenida en la práctica durante el cuatrimestre.
Un alumno que no entregue la práctica puede presentarse sin problema al examen presencial, pero teniendo en cuenta que se le aplicarán los porcentajes anteriores.
No será necesario que el alumno acuda al Centro Asociado para realizar la práctica ya que ésta podrá hacerse en su totalidad a distancia y se entregará a través del curso virtual. |
How to obtain the final grade?
|
Para calcular la nota final de la asignatura se sumarán las notas obtenidas en la prueba presencial y en la práctica con los siguientes pesos:
-Prueba presencial: 90% (supondrá, por tanto, un máximo de 9 puntos en la nota final de la asignatura).
-Práctica de laboratorio: 10% (supondrá, por tanto, un máximo de 1 punto en la nota final de la asignatura). IMPORTANTE: Hay que obtener una nota mínima de 5 puntos en la prueba presencial para que se tome en consideración la calificación de la práctica. |
Este texto cubre la totalidad de los contenidos teóricos previstos para la asignatura. Los alumnos dispondrán de unos apuntes con un plan de trabajo que adapte el libro a los contenidos y créditos previstos en la asignatura.
T. García Saiz y E. Gaudioso Vázquez Autómatas, Gramáticas y Lenguajes formales: problemas resueltos. Sanz y Torres, 2010
Por lo general, los textos que cubren esta materia, lo hacen desde un enfoque teórico proponiendo ejercicios para cada tema que debe resolver el lector. Sin embargo, es difícil encontrar ejercicios completos que recorran, para un mismo problema todas las posibilidades de representación y la equivalencia entre las mismas. El objetivo de este libro es el de plantear y resolver este tipo de ejercicios.
Aunque la profundidad de estos ejercicios sobrepasa los objetivos de la asignatura, puede ser de utilidad para los estudiantes que quieran profundizar en la materia.
J.E. Hopcroft, J. D. Ullman y R. Motwani. Teoría de autómatas, lenguajes y computación. Pearson Addison-Wesley.
Libro de referencia en el área de autómatas, lenguajes y computación. Es útil a la hora de profundizar conocimientos, sobre todo desde el punto de vista de las demostraciones formales de los enunciados que se ven en la asignatura.
Aunque en esta asignatura no tiene entre sus objetivos profundizar en las demostraciones formales, puede ser de utilidad para los estudiantes que quieran profundizar en la materia.
J. Glenn Brookshear. Teoría de la computación. Lenguajes formales, autómatas y complejidad Addison-Wesley, 1993.
Algunos de los contenidos teóricos del texto se pueden complementar con los incluidos en este texto que presenta, además, ejemplos prácticos adicionales. De nuevo puede ser de utilidad para los estudiantes que quieran profundizar en la material.
P. Isasi, P. Martínez y D. Borrajo. Lenguajes, gramáticas y autómatas: un enfoque práctico. Addison Wesley. ISBN: 0-201-65323-0
Este texto es de utilidad para complementar el estudio de la asignatura con problemas resueltos.
Los alumnos dispondrán de los siguientes recursos de apoyo al estudio:
- Curso virtual. A través de esta plataforma los alumnos tienen la posibilidad de:
- Consultar información de la asignatura.
- Realizar consultas al equipo docente a través de los foros correspondientes.
- Consultar material adicional proporcionado por el equipo docente (apuntes y ejercicios resueltlos).
- Tutorías en los Centros Asociados al que pertenezca el alumno. Cada alumno puede consultar si existe la posibilidad de disponer de una tutoría presencial con un tutor que atienda presencialmente a los estudiantes (aclarando, orientando y resolviendo dudas)
- Atención telefónica, presencial o por videollamada. Los alumnos pueden contactar y realizar consultas al equipo docente en los teléfonos y horarios que se indican en esta guía.
- Biblioteca. En el Centro Asociado al que pertenezca el alumno, o bien, en la Sede Central los estudiantes podrán consultar la bibliografía básica y la complementaria de la asignatura.
