NO EXISTEN CAMBIOS
The subject guide has been updated with the changes mentioned here
| SUBJECT NAME |
| SUBJECT NAME |
AUTÓMATAS, GRAMÁTICAS Y LENGUAJES |
| CODE |
| CODE |
71901089 |
| SESSION |
| SESSION |
2024/2025 |
| DEPARTMENT |
| DEPARTMENT |
INTELIGENCIA ARTIFICIAL
|
| DEGREE IN WHICH IT IS OFFERED |
| DEGREE IN WHICH IT IS OFFERED |
|
|
|
GRADO EN INGENIERÍA INFORMÁTICA
|
| COURSE - PERIOD - TYPE |
-
PRIMER
-
SEMESTER 2
- OBLIGATORIAS
|
|
GRADO EN INGENIERÍA EN TECNOLOGÍAS DE LA INFORMACIÓN
|
| COURSE - PERIOD - TYPE |
- ESPECÍFICO PARA INGENIEROS TÉCNICOS EN INFORMÁTICA DE GESTIÓN EN UNED
-
OPTATIVAS
-
SEMESTER 2
- OBLIGATORIAS
- ESPECÍFICO PARA INGENIEROS TÉCNICOS EN INFORMÁTICA DE GESTIÓN
-
OPTATIVAS
-
SEMESTER 2
- OBLIGATORIAS
- GRADO EN INGENIERÍA EN TECNOLOGÍAS DE LA INFORMACIÓN
-
PRIMER
COURSE
-
SEMESTER 2
- OBLIGATORIAS
|
| CREDITS NUMBER |
| CREDITS NUMBER |
6 |
| HOURS |
| HOURS |
150 |
| LANGUAGES AVAILABLE |
| LANGUAGES AVAILABLE |
CASTELLANO |
La asignatura “Autómatas, Gramáticas y Lenguajes” se ocupa del estudio 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, competencias que trabaja, conocimientos previos recomendables y resultados esperados de aprendizaje. En concreto, se recomienda al alumno que visite el apartado de Evaluación, ya que, debido a que esta asignatura se enmarca dentro del marco definido por el Espacio Europeo de Educación Superior, parte de la asignatura se evaluará utilizando un método de evaluación continua. Por ello, la calificación de prácticas tendrá un peso en la calificación final de la asignatura.
Esta asignatura es común a los grados en Ingeniería Informática y en Ingeniería de las Tecnologías de la Información y de carácter obligatorio en ambas titulaciones. Se imparte en el segundo cuatrimestre del primer curso, consta de 6 créditos ECTS y es parte de la materia de Lenguajes de Programación. Dentro de esta materia es la primera de las asignaturas que se cursa.
El conocimiento de sus contenidos es necesario para cursar las asignaturas de Teoría de los Lenguajes de Programación y Procesadores de Lenguajes I y II en el Grado en Ingeniería Informática y de Lenguajes de Programación y Procesadores en el Grado de Ingeniería de las Tecnologías de la Información. Así mismo, esta asignatura tiene su continuidad en la asignatura obligatoria Complejidad y Computabilidad en el grado en Ingeniería Informática.
Esta asignatura se sitúa, por tanto, en el nivel básico dentro del plan de formación de los grados en Ingeniería Informática y en Tecnologías de la Información 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.
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.
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.
Horario de Asistencia al estudiante: miércoles y juevesde 10 a 14 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
Horario de Atención al Estudiante: Lunes y Martes de 09 a 13 h
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
De acuerdo a la memoria de verificación del grado (disponible desde www.ii.uned.es) la siguiente asignatura trabaja las siguientes competencias generales y específicas:
- Competencias Generales
- (G.2) Competencias cognitivas superiores: selección y manejo adecuado de conocimientos, recursos y estrategias cognitivas de nivel superior apropiados para el afrontamiento y resolución de diversos tipos de tareas/problemas con distinto nivel de complejidad y novedad: Análisis y Síntesis. Aplicación de los conocimientos a la práctica Resolución de problemas en entornos nuevos o poco conocidos. Pensamiento creativo. Razonamiento crítico. Toma de decisiones.
- (G.4) Competencias de expresión y comunicación. Comunicación y expresión matemática, científica y tecnológica
- (G.5) Competencias en el uso de las herramientas y recursos de la Sociedad del Conocimiento: Competencia en la búsqueda de información relevante. Competencia en la recolección de datos, el manejo de bases de datos y su presentación
- Competencias Específicas
- (BTEc.2) 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.
- (BC.1) Capacidad para diseñar, desarrollar, seleccionar y evaluar, aplicaciones y sistemas informáticos, asegurando su fiabilidad, seguridad y calidad, conforme a los principios éticos y a la legislación y normativa vigente.
- (BC.6) Conocimiento y aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y complejidad de los algoritmos propuestos.
- (BC.8) Capacidad para analizar, diseñar, construir y mantener aplicaciones de forma robusta, segura y eficiente, eligiendo el paradigma y los lenguajes de programación más adecuados.
- (BC.9) Capacidad para conocer, comprender y evaluar la estructura y arquitectura de los computadores, así como los componentes básicos que los conforman.
- (BTEc.1) Capacidad para tener un conocimiento profundo de los principios fundamentales de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar, y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática.
- (FB.5) Conocimiento de la estructura, organización, funcionamiento e interconexión de los sistemas informáticos, así como de los fundamentos de su programación, y su aplicación para la resolución de problemas propios de la ingeniería.
- (FB.4) Conocimientos básicos sobre el uso y programación de los ordenadores, sistemas operativos, bases de datos y programas informáticos con aplicación en ingeniería.
- (BC.7) Conocimiento, diseño y utilización de forma eficiente de los tipos y estructuras de datos más adecuados a la resolución de un problema.
Los resultados que se pretenden alcanzar con el estudio de esta asignatura son:
- Conocer y comprender los distintos tipos de autómatas, gramáticas y lenguajes que reconocen. Más concretamente: Conocer la equivalencia entre lenguajes y gramáticas de los diferentes autómatas (autómatas finitos y autómatas de pila); Conocer el funcionamiento de los diferentes autómatas: autómatas finitos y autómatas de pila; Reconocer el lenguaje reconocido por cualquier autómata; Conocer los límites de los diferentes autómatas como reconocedores de lenguajes (jerarquía de lenguajes de Chomsky); Conocer el funcionamiento básico de las máquinas de Turing; Conocer límites de la computabilidad: Tesis de Turing.
- Diseñar y construir gramáticas y autómatas. Más concretamente: Conocer los mecanismos de representación de los autómatas; Conocer la representación formal de los diferentes autómatas: autómatas finitos, autómatas de pila y máquinas de Turing
Tema 1: Introducción a la asignatura y repaso a la teoría de conjuntos
En este bloque se hará una introducción a la asignatura y un repaso de los contenidos básicos de la teoría de conjuntos. Aunque no debería revestir dificultad, conviene hacer un repaso pausado de los conceptos de teoría de conjuntos proporcionados en el libro base de la asignatura, en especial la definición formal de los elementos de un conjunto y las operaciones entre conjuntos.
Tema 2: Autómatas Finitos
En este bloque se inicia el estudio de los autómatas. Es importante hacer un estudio cuidadoso de los elementos que definen un autómata. En especial, al inicio, suele conllevar cierta dificultad entender el funcionamiento de las máquinas teóricas. Se recomienda hacer hincapié en el funcionamiento de estos autómatas más sencillos para poder entender mejor el resto de la asignatura.
Tema 3: Gramáticas regulares
En este bloque se inicia el estudio de gramáticas como generadoras de lenguajes. Es importante conocer los elementos de una gramática y en especial cómo funcionan las derivaciones. Este último punto suele revestir algo de dificultad porque suele ser la primera vez que se realizan este tipo de operaciones.
Tema 4: Expresiones Regulares
En este bloque se estudia otra manera de representar los lenguajes regulares. Es importante conocer su definición y las operaciones entre expresiones regulares. Éstas últimas, aunque similares a las operaciones entre conjuntos, requieren un estudio más pausado.
Tema 5: Propiedades de los lenguajes regulares y lenguajes no regulares
Una vez conocidos los lenguajes regulares y como representarlos mediante autómatas, gramáticas regulares y expresiones regulares, en este bloque se estudian sus propiedades. Aunque estos contenidos no deberían revestir dificultad, si es necesario pararse a estudiar qué tipo de lenguaje resulta de las operaciones entre lenguajes regulares.
Se introduce además una propiedad que deben cumplir los lenguajes regulares (i.e. lema de bombeo para lenguajes regulares). La aplicación de esta propiedad puede resultar algo complicada y conviene tener claro para qué se utiliza, sobre todo de cara a los lenguajes independientes del contexto.
Tema 6: Gramáticas independientes del contexto
En este bloque se continua con el estudio de las gramáticas más generales que las vistas en el tema 3. Se trata de las gramáticas independientes del contexto. Una vez claros los conceptos vistos para las gramáticas regulares, este tema no debería entrañar demasiada dificultad. Es importante tener clara la diferencia entre derivaciones por la derecha y por la izquierda y la diferencia con las gramáticas regulares.
Tema 7: Autómatas a pila
En este bloque se estudiarán los autómatas a pila que tienen un mayor poder de reconocimiento que los autómatas finitos vistos al inicio. Una vez sabidos los elementos fundamentales de un autómata, conviene hacer un estudio pausado del funcionamiento de la pila en estos autómatas, que al principio puede resultar algo extraño.
Tema 8: Propiedades de los lenguajes independientes del contexto
Al igual que se hizo en el tema 5, en este bloque se estudian las propiedades de los lenguajes independientes del contexto. De nuevo, aunque estos contenidos no deberían revestir dificultad, si es necesario pararse a estudiar qué tipo de lenguaje resulta de las operaciones entre lenguajes independientes del contexto.
Se continua además con el estudio del lema de bombeo para lenguajes independientes del contexto. La aplicación de esta propiedad puede resultar algo complicada y conviene tener claro para qué se utiliza, sobre todo de cara a los lenguajes independientes del contexto.
Tema 9: Introducción a las Máquinas de Turing
Una vez conocidos los autómatas finitos y de pila, en este bloque se introduce el estudio de las máquinas de Turing. En esta asignatura sólo se ve una introducción a estas máquinas pero conviene conocer sus elementos fundamentales y sobre todo la diferencia de funcionamiento: operaciones de desplazamiento (a la derecha y a la izquierda) y operaciones de escritura. Estas diferencias suelen entrañar alguna dificultad que se trata de solventar con ejemplos prácticos.
La metodología seguida en esta asignatura se ajusta a la metodología prevista para el estudio a distancia en la UNED. Así, además de un libro base en el que se recogen todos los contenidos que se deben adquirir, el estudiante tiene a su disposición los siguientes recursos:
- Centros asociados: donde acudir a consultar dudas tanto administrativas como de docencia (las tutorías podrán ser on-line o presenciales según los centros). En estos centros se realiza además las pruebas presenciales.
- Curso virtual: gestionado por el equipo docente, proporciona recursos adicionales tales como, ejercicios resueltos, vídeos explicativos y foros de consulta atendidos por los profesores.
- Tutorías con el equipo docente: siempre que un estudiante lo solicite tiene la disponibilidad de consultar sus dudas, tanto presencialmente (en la sede central de Madrid) como a distancia (bien por teléfono o por videollamada) al equipo docente de la Sede Central. En el apartado de equipo docente y horario de atención puede consultar los datos de contacto para solicitar la tutoría.
- Evaluación: en el apartado de evaluación dispone de la información necesaria para conocer la metodología de evaluación y las pruebas previstas.
Más particularmente, la metodología prevista para esta asignatura incluye: trabajo con contenidos teórico-prácticos utilizando la bibliografía de la asignatura, trabajo autónomo con las actividades de ejercicios prácticos, y realización de una prueba de evaluación a distancia con las herramientas y directrices preparadas por el equipo docente y corregidas por un profesor tutor. De manera orientativa, la distribución porcentual del trabajo en cada una de las actividades formativas es la siguiente:
- Trabajo con contenidos teóricos; consulta de materiales didácticos: 30 %
- Trabajo autónomo: estudio de contenidos teóricos, realización de la práctica, preparación de las pruebas presenciales, consulta de dudas: 70 %
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 |
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: 80% (supondrá, por tanto, un máximo de 8 puntos en la nota final de la asignatura). -Prueba de evaluación continua: 20% (supondrá, por tanto, un máximo de 2 puntos en la nota final de la asignatura). Para poder contabilizar la nota de la práctica, se exigirá una puntuación mínima de 5 puntos en la prueba presencial. La calificación final de la asignatura se calculará teniendo en cuenta los porcentajes explicados anteriormente. Para aprobar la asignatura es necesario obtener una calificación final mayor o igual a 5 puntos. Un alumno que no entregue la práctica puede presentarse al examen pero al calcular la nota final de la asignatura se tendrán en cuenta los porcentajes indicados anteriormente. |
| % Concerning the final grade |
| % Concerning the final grade |
80 |
| Minimum grade (not including continuas assessment) |
| Minimum grade (not including continuas assessment) |
6,2 |
| Maximum grade (not including continuas assessment) |
| Maximum grade (not including continuas assessment) |
8 |
| Minimum grade (including continuas assessment) |
| Minimum grade (including continuas assessment) |
5 |
| 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á 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. La práctica se entregará a través del curso virtual y será corregida por un profesor tutor. |
CONTINUOUS ASSESSMENT TEST (PEC)
|
| PEC? |
| PEC? |
Si |
| Description |
| Description |
En esta asignatura está prevista la realización de una única prueba de evaluación continua. El objetivo de esta práctica es afianzar los conocimientos adquiridos por los alumnos. La práctica estará compuesta por ejercicios prácticos de resolución de “Autómatas Finitos” y de “Autómatas a Pila” . La carga dedicada a cada uno de los dos temas estará nivelada. La fecha de entrega prevista de esta práctica será aproximadamente durante la 11º semana del curso. La fecha definitiva de entrega se publicará junto al enunciado en el curso virtual al inicio del cuatrimestre. |
| Assessment criteria |
| Assessment criteria |
La nota de la Prueba de Evaluación Continua (PEC) tiene un peso del 20% en la calificación final de la asignatura. El equipo docente proporcionará las soluciones que utilizarán los profesores tutores en la evaluación de la PEC. Dichas soluciones junto con los criterios de evaluación estarán disponibles tanto para los profesores tutores como para los estudiantes. |
| Weighting of the PEC in the final grade |
| Weighting of the PEC in the final grade |
20 |
| 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. La práctica se entregará a través del curso virtual y será corregida por un profesor tutor. |
OTHER GRADEABLE ACTIVITIES
|
| Are there other evaluable activities? |
| Are there other evaluable activities? |
No |
| Description |
| Description |
|
| Assessment criteria |
| Assessment criteria |
|
| Weighting in the final grade |
| Weighting in the final grade |
0 |
| Approximate submission date |
| Approximate submission date |
|
| Coments |
| Coments |
|
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: 80% (supondrá, por tanto, un máximo de 8 puntos en la nota final de la asignatura). -Prueba de Evaluación Continua: 20% (supondrá, por tanto, un máximo de 2 puntos en la nota final de la asignatura). |
Este texto cubre la totalidad de los contenidos teóricos previstos para la asignatura. Los alumnos dispondrán de un plan de trabajo en el que se especificará una sugerencia de planificación.
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.
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.
J. Glenn Brookshear. Theory of Computation: Formal Languages, automata and complexity. 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. Las referencias a este texto se recomendarán en el plan de trabajo del que dispondrán los alumnos matriculados. Se recomienda el texto en inglés porque la edición en castellano se encuentra descatalogada.
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 o del correo electrónico.
- Consultar material adicional proporcionado por el equipo docente (principalmente batería de prácticas y exámenes resueltos de años anteriores).
- Tutorías en los Centros Asociados al que pertenezca el alumno. Cada alumno deberá 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 y presencial. 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.
