Teoría de Autómatas y Lenguajes Formales

Introducir los conceptos de la teoría de autómatas y de los lenguajes formales, y estudiar sus aplicaciones. En la asignatura se realizará el estudio de los diferentes modelos de máquinas computacionales, gramáticas y lenguajes formales, así como la correspondencia entre autómatas, lenguajes y gramáticas. También se estudiarán los conceptos de decidibilidad y complejidad computacional.

PROGRAMA DE TEORÍA

1. Introducción: lenguajes, gramáticas formales, autómatas


2. Autómatas finitos

Autómatas finitos deterministas (AFD)
Autómatas finitos no deterministas (AFN)
Transformación de AFN en AFD
Minimización de AFD


3. Lenguajes regulares

Expresiones regulares
Autómatas finitos y expresiones regulares
Álgebra de expresiones regulares
Lema de bombeo para lenguajes regulares


4. Gramáticas independientes del contexto (GIC)

Definición de gramáticas
Derivaciones
Árboles de derivación
Ambigüedad
Formas normales para GIC


5. Autómatas con pila

Autómatas con pila no deterministas
Reconocimiento por vaciado de pila y por estado final
Transformación de gramáticas a autómatas con pila
Autómatas con pila deterministas
Lema de bombeo para lenguajes independientes del contexto (LIC)


6. Máquinas de Turing

Máquina de Turing básica
Extensiones a la máquina de Turing básica
Máquinas de Turing restringidas


7. Decidibilidad y complejidad

Lenguajes recursivos y recursivamente enumerables
Problemas indecidibles
Problemas intratables: las clases P y NP
Problemas NP-completos


PROGRAMA DE PRÁCTICAS

El programa de prácticas se divide en tres bloques:

1. Autómatas de estados finitos y expresiones regulares

2. Autómatas con pila y gramáticas independientes del contexto

3. Máquinas de Turing

Básica

LINZ, Peter. Introduction to formal languages and automata. Ed. 3, Boston: Jones and Bartlett Publishers, 2006. ISBN 978-0-7637-3798-6.

HOPCROFT, John E., MOTWANI, Rajeev, ULLMAN, Jeffrey D. Teoría de Autómatas, Lenguajes y Computación. Ed. 3, Madrid: Pearson Educación, 2008. ISBN 978-84-7829-088-8.


Complementaria


ALFONSECA CUBERO, Enrique, ALFONSECA MORENO, Manuel, MORIYÓN SALOMÓN, Roberto. Teoría de Autómatas y Lenguajes Formales. Ed. 1, Madrid: McGraw Hill, 2007. ISBN 978-84-481-5637-4.

SUDKAMP, Thomas A. Languages and machines: an introduction to the theory of computer science. Ed. 3, Boston: Pearson, 2006. ISBN 978-0-321-32221-0.

Las competencias desarrolladas en la materia se agrupan en 4 bloques (BC), indicándose para cada uno de ellos los códigos de las competencias asociadas en la memoria del Grado en Ingeniería Informática:

(BC1) Modelos de computación. Conocer y comprender la capacidad que aportan los distintos modelos abstractos de computación [competencia específica].

(BC2) Decidibilidad y complejidad. Capacidad para comprender y dominar los conceptos básicos de complejidad computacional, y su aplicación para la resolución de problemas propios de la ingeniería [FB3]. 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 [RI6]. Conocer y comprender los fundamentos y límites de la computación, y así la existencia de problemas computables y no computables, y entre los primeros, la existencia de problemas tratables e intratables [competencia específica].

(BC3) Resolución de problemas. Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad [CG9]. Capacidad de análisis y síntesis; resolución de problemas [TR1].

(BC4) Creatividad [TR3].

Clases de teoría.

Se elaborará material de estudio para cada uno de los temas, de tal forma que el alumnado pueda seguir la clase. En las transparencias también se incluyen problemas, algunos de los cuales serán resueltos en clase, mientras que otros deberá solucionarlos el propio alumnado dentro de su tiempo de estudio de la asignatura. Muchos de los ejercicios han sido extraídos de exámenes de años anteriores.


Sesiones de prácticas.

Las sesiones de prácticas serán de dos horas de duración, y se propondrán boletines a modo de guía de las mismas. Antes de acudir a cada sesión de prácticas es imprescindible haber estudiado la teoría correspondiente. También es aconsejable que el/la alumno/a haya resuelto por su cuenta algún problema del tema.

La competencia BC1 (modelos de computación) se trabajará en todos los temas de la materia. Se conocerán y comprenderán los diferentes modelos de computación: autómatas de estados finitos, autómatas con pila, autómatas linealmente acotados, y máquinas de Turing. Además, se estudiarán también las distintas gramáticas: regulares, independientes del contexto, sensibles al contexto y sin restricciones.

La competencia BC2 (decidibilidad y complejidad) se desarrollará en el último bloque de la asignatura: máquinas de Turing, decidibilidad y complejidad. Para ello se conocerán y comprenderán los fundamentos y límites de la computación, y así la existencia de problemas computables y no computables, y entre los primeros, la existencia de problemas tratables e intratables.

La competencia BC3 (resolución de problemas) se trabajará en todos los temas de la asignatura, salvo el de introducción. Gran parte de los contenidos teóricos de la materia que se estudiarán a lo largo del curso serán aplicados para la resolución de problemas. De igual forma, la mayoría de los boletines de prácticas consistirán en una serie de problemas que el alumno debe resolver (diseño de autómatas y gramáticas, aplicación del lema del bombeo, etc.). Por tanto, para el estudio de la asignatura se potenciará el aprendizaje autónomo del alumno mediante la solución de problemas que plantee el profesor en la clase, o bien de aquellos que se proponen en la bibliografía recomendada para la materia.

La competencia BC4 (creatividad) se desarrollará en los temas en los que se diseñen autómatas o gramáticas, y también en la aplicación del lema de bombeo. Un alto porcentaje de los problemas/prácticas que se plantean en la asignatura requieren de una cierta dosis de creatividad. Así ocurre con el diseño de los distintos tipos de autómatas (de estados finitos, con pila, máquinas de Turing) y gramáticas, o incluso con la aplicación del lema de bombeo. La creatividad es una competencia que el alumno necesita, debe, y puede trabajar resolviendo ejercicios y realizando las prácticas.


Dinámica de actividades.

Sesiones expositivas:

1. Tema 1. Introducción.
2. Tema 2. Autómatas finitos: autómatas finitos deterministas (AFD).
3. Tema 2. Autómatas finitos: autómatas finitos no deterministas (AFN).
4. Tema 2. Autómatas finitos: AFN (continuación).
5. Tema 2. Autómatas finitos: transformación de AFN en AFD.
6. Tema 2. Autómatas finitos: minimización de AFD.
7. Tema 3. Lenguajes regulares: expresiones regulares.
8. Tema 3. Lenguajes regulares: autómatas finitos y expresiones regulares.
9. Tema 3. Lenguajes regulares: autómatas finitos y expresiones regulares (continuación).
10. Tema 3. Lenguajes regulares: álgebra de expresiones regulares.
11. Tema 3. Lenguajes regulares: lema de bombeo para lenguajes regulares.
12. Tema 4. Gramáticas independientes del contexto (GIC): definición de gramáticas.
13. Tema 4. Gramáticas independientes del contexto (GIC): derivaciones.
14. Tema 4. Gramáticas independientes del contexto (GIC): árboles de derivación; ambigüedad.
15. Tema 4. Gramáticas independientes del contexto (GIC): formas normales para GIC.
16. Tema 4. Gramáticas independientes del contexto (GIC): formas normales para GIC (continuación).
17. Tema 5. Autómatas con pila: autómatas con pila no deterministas.
18. Tema 5. Autómatas con pila: reconocimiento por vaciado de pila y por estado final; transformación de gramáticas a autómatas con pila.
19. Tema 5. Autómatas con pila: autómatas con pila deterministas; lema de bombeo para lenguajes independientes del contexto (LIC).
20. Tema 6. Máquinas de Turing: máquina de Turing básica.
21. Tema 6. Máquinas de Turing: máquina de Turing básica (continuación).
22. Tema 6. Máquinas de Turing: extensiones a la máquina de Turing básica.
23. Tema 6. Máquinas de Turing: máquinas de Turing restringidas.
24. Tema 7. Decidibilidad y complejidad: lenguajes recursivos y recursivamente enumerables.
25. Tema 7. Decidibilidad y complejidad: problemas indecidibles; problemas intratables: las clases P y NP; problemas NP-completos.


Sesiones interactivas -de entre las siguientes, en función de la evolución del curso-:

1. Diseño de autómatas de estados finitos.
2. Aplicaciones reales de los autómatas de estados finitos.
3. Minimización de autómatas de estados finitos, y expresiones regulares.
4. Lema de bombeo para lenguajes regulares.
5. Diseño de gramáticas independientes del contexto.
6. Diseño de gramáticas independientes del contexto y Forma Normal de Chomsky.
7. Diseño de autómatas con pila por estado final.
8. Diseño de autómatas con pila por vaciado de pila.
9. Lema de bombeo para lenguajes independientes del contexto.
10. Diseño de máquinas de Turing estándar (i).
11. Diseño de máquinas de Turing estándar (ii).
12. Diseño de gramáticas sensibles al contexto (GSC) y gramáticas sin restricciones (GSR).

La evaluación de la asignatura se realizará en dos partes: evaluación continua y examen final. Para aprobar la asignatura es imprescindible superar ambas partes por separado.

La evaluación continua se realizará mediante la entrega de los boletines de prácticas correspondientes a cada sesión, así como por medio de test con preguntas relativas a los boletines entregados. Estos test se realizarán de forma presencial durante las clases de prácticas. El peso máximo de los boletines de prácticas en la evaluación continua será de 7 puntos. Además, a lo largo del curso se realizarán exámenes parciales que permitirán sumar hasta 3 puntos en total. La nota máxima que se puede obtener en la evaluación continua será de 10 puntos.

En el examen final escrito el alumno podrá lograr un máximo de 10 puntos.

La nota final de la materia será la media aritmética de la evaluación continua y el examen final, excepto en aquellas situaciones en las que no se haya aprobado alguna de las dos partes, en cuyo caso la nota final será el mínimo entre la evaluación continua y el examen final, debiendo volver a evaluarse de acuerdo con lo indicado posteriormente.

La entrega de alguno de los boletines de prácticas o de alguna de las pruebas de evaluación continua supondrá que el alumno optó por presentarse a la asignatura. Por tanto, a partir de ese momento, aún no presentándose al examen final habrá consumido una oportunidad.

En la segunda oportunidad (julio) se conservarán las notas de la evaluación continua obtenidas durante el cuatrimestre, en caso de tener una calificación de la misma de 4 o más puntos, en cuyo caso la calificación global será la media aritmética entre dicha calificación y la obtenida en el examen de teoría de la segunda oportunidad. En otro caso el estudiante tendrá también que ser evaluado de nuevo de la parte de prácticas de la materia en esta segunda oportunidad.

En el caso de realización fraudulenta de ejercicios o pruebas, será de aplicación lo recogido en la normativa de evaluación del rendimiento académico de los estudantes y de revisión de las calificaciones (https://www.xunta.gal/dog/Publicados/2011/20110721/AnuncioG2018-190711-…). En aplicación de la normativa de la ETSE sobre plagio (aprobada por la Xunta da ETSE el 19/12/2019), la copia total o parcial de algún ejercicio de prácticas o teoría supondrá el suspenso de las dos oportunidades del curso, con la caificación de 0,0 en ambos casos (https://www.usc.es/etse/files/u1/NormativaPlagioETSE2019.pdf).

La evaluación de las competencias se realizará en las siguientes prácticas/exámenes:

[CE1] Todas las prácticas y exámenes.
[FB3, RI6, CE2] Prácticas, exámenes parciales y examen final.
[CG9, TR1] Todas las prácticas y exámenes.
[TR3] Todas las prácticas y exámenes.

El tiempo de trabajo del alumno en la asignatura a lo largo del curso se desglosa del siguiente modo:

(1) 25 horas de asistencia a las clases teóricas (2h/semana en general, con alguna excepción).

(2) 25 horas de asistencia a clases de prácticas (2h/semana en general, con alguna excepción).

(3) 7,5 horas dedicadas a la realización de actividades de evaluación (exámenes parciales y final).

(4) 85 horas de estudio autónomo y de realización de trabajos y prácticas (5-6h/semana).

(5) 7,5 horas de evaluación de trabajos y prácticas mediante test.

Se recomienda llevar el estudio de la teoría y la realización de prácticas y problemas al día, puesto que la evaluación mediante test así lo requiere. Igualmente se considera importante hacer un uso intenso de las tutorías para la resolución de dudas.

Se utilizará el Campus Virtual de la USC como herramienta de apoyo al proceso de aprendizaje en los siguientes aspectos: repositorio de materiales (transparencias, ejercicios, textos complementarios...), entrega y evaluación comentada de trabajos obligatorios y tutorización virtual (correo electrónico y foros).

Para la realización de parte de las prácticas se empleará el software JFLAP, que permite el diseño de autómatas y gramáticas, o aplicar el lema de bombeo, entre otras funcionalidades.

La lengua predominante de impartición de la materia será el gallego.