Teoría de Autómatas e Linguaxes Formais

Introducir os conceptos da teoría de autómatas e das linguaxes formais, e estudar as súas aplicacións. Na materia realizarase o estudo dos diferentes modelos de máquinas computacionais, gramáticas e linguaxes formais, así como a correspondencia entre autómatas, linguaxes e gramáticas. Tamén estudaranse os conceptos de decidibilidade e complexidade computacional.

PROGRAMA DE TEORÍA

1. Introdución: linguaxes, gramáticas formais, autómatas


2. Autómatas finitos

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


3. Linguaxes regulares

Expresións regulares
Autómatas finitos e expresións regulares
Álxebra de expresións regulares
Lema de bombeo para linguaxes regulares


4. Gramáticas independentes do contexto (GIC)

Definición de gramáticas
Derivacións
Árbores de derivación
Ambigüidade
Formas normais para GIC


5. Autómatas con pila

Autómatas con pila non deterministas
Recoñecemento por baleirado de pila e por estado final
Transformación de gramáticas a autómatas con pila
Autómatas con pila deterministas
Lema de bombeo para linguaxes independentes do contexto (LIC)


6. Máquinas de Turing

Máquina de Turing básica
Extensións á máquina de Turing básica
Máquinas de Turing restrinxidas


7. Decidibilidade e complexidade

Linguaxes recursivas e recursivamente enumerables
Problemas indecidibles
Problemas intratables: as clases P e NP
Problemas NP-completos


PROGRAMA DE PRÁCTICAS

O programa de prácticas divídese en tres bloques:

1. Autómatas de estados finitos e expresións regulares

2. Autómatas con pila e gramáticas independentes do 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.

As competencias desenvolvidas na materia agrúpanse en 4 bloques (BC), indicándose para cada un deles os códigos das competencias asociadas na memoria do Grao en Enxeñaría Informática:

(BC1) Modelos de computación. Coñecer e comprender a capacidade que aportan os distintos modelos abstractos de computación [competencia específica].

(BC2) Decidibilidade e complexidade. Capacidade para comprender e dominar os conceptos básicos de complexidade computacional, e a súa aplicación para a resolución de problemas propios da enxeñaría [FB3]. Coñecemento e aplicación dos procedementos algorítmicos básicos das tecnoloxías informáticas para deseñar solucións a problemas, analizando a idoneidade e complexidade dos algoritmos propostos [RI6]. Coñecer e comprender os fundamentos e límites da computación, e así a existencia de problemas computables e non computables, e entre os primeiros, a existencia de problemas tratables e intratables [competencia específica].

(BC3) Resolución de problemas. Capacidade para resolver problemas con iniciativa, toma de decisións, autonomía e creatividade [CG9]. Capacidade de análise e síntese; resolución de problemas [TR1].

(BC4) Creatividade [TR3].

Clases de teoría.

Elaborarase material de estudo para cada un dos temas, de tal forma que o alumnado poida seguir a clase. Nas transparencias tamén se inclúen problemas, algúns dos cales serán resoltos en clase, mentres que outros deberá solucionalos o propio alumnado dentro do seu tempo de estudo da materia. Moitos dos exercicios foron extraídos de exames de anos anteriores.


Sesións de prácticas.

As sesións de prácticas serán de dúas horas de duración, e proporanse múltiples boletíns a modo de guía. Antes de acudir a cada sesión de prácticas é imprescindible estudar a teoría correspondente. Tamén é aconsellable que o alumno resolva pola súa conta algún problema do tema.

A competencia BC1 (modelos de computación) traballarase en todos os temas da materia. Coñeceranse e comprenderanse os diferentes modelos de computación: autómatas de estados finitos, autómatas con pila, autómatas linealmente acoutados, e máquinas de Turing. Ademais, estudaranse tamén as distintas gramáticas: regulares, independentes do contexto, sensibles ao contexto e sen restriccións.

A competencia BC2 (decidibilidade e complexidade) desenvolverase no último bloque da asignatura: máquinas de Turing, decidibilidade e complexidade. Para iso coñeceranse e comprenderanse os fundamentos e límites da computación, e así a existencia de problemas computables e non computables, e entre os primeiros, a existencia de problemas tratables e intratables.

A competencia BC3 (resolución de problemas) traballarase en todos os temas da asignatura, salvo o de introdución. Gran parte dos contidos teóricos da materia que se estudarán ao longo do curso serán aplicados para a resolución de problemas. De igual forma, a maioría dos boletíns de prácticas consistirán nunha serie de problemas que o alumno debe resolver (deseño de autómatas e gramáticas, aplicación do lema do bombeo, etc.). Xa que logo, para o estudo da asignatura se potenciará a aprendizaxe autónoma do alumno mediante a solución de problemas que plantexe o profesor na clase, ou ben daqueles que se propoñen na bibliografía recomendada para a materia.

A competencia BC4 (creatividade) desenvolverase nos temas nos que se deseñen autómatas ou gramáticas, e tamén na aplicación do lema de bombeo. Unha alta porcentaxe dos problemas/prácticas que se plantexan na asignatura requiren dunha certa dose de creatividade. Así ocorre co deseño dos distintos tipos de autómatas (de estados finitos, con pila, máquinas de Turing) e gramáticas, ou ata coa aplicación do lema de bombeo. A creatividade é unha competencia que o alumno necesita, debe, e pode traballar resolvendo exercicios e realizando as prácticas.


Dinámica de actividades.

Sesións expositivas:

1. Tema 1. Introdución.
2. Tema 2. Autómatas finitos: autómatas finitos deterministas (AFD).
3. Tema 2. Autómatas finitos: autómatas finitos non 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. Linguaxes regulares: expresións regulares.
8. Tema 3. Linguaxes regulares: autómatas finitos e expresións regulares.
9. Tema 3. Linguaxes regulares: autómatas finitos e expresións regulares (continuación).
10. Tema 3. Linguaxes regulares: álxebra de expresións regulares.
11. Tema 3. Linguaxes regulares: lema de bombeo para linguaxes regulares.
12. Tema 4. Gramáticas independentes do contexto (GIC): definición de gramáticas.
13. Tema 4. Gramáticas independentes do contexto (GIC): derivacións.
14. Tema 4. Gramáticas independentes do contexto (GIC): árbores de derivación; ambigüidade.
15. Tema 4. Gramáticas independentes do contexto (GIC): formas normais para GIC.
16. Tema 4. Gramáticas independentes do contexto (GIC): formas normais para GIC (continuación).
17. Tema 5. Autómatas con pila: autómatas con pila non deterministas.
18. Tema 5. Autómatas con pila: recoñecemento por baleirado de pila e 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 linguaxes independentes do 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: extensións á máquina de Turing básica.
23. Tema 6. Máquinas de Turing: máquinas de Turing restrinxidas.
24. Tema 7. Decidibilidade e complexidade: linguaxes recursivos e recursivamente enumerables.
25. Tema 7. Decidibilidade e complexidade: problemas indecidibles; problemas intratables: as clases P e NP; problemas NP-completos.


Sesións interactiva -a desenvolver segundo a evolución do curso-

1. Deseño de autómatas de estados finitos.
2. Aplicacións reais dos autómatas de estados finitos.
3. Minimización de autómatas de estados finitos, e expresións regulares.
4. Lema de bombeo para linguaxes regulares.
5. Deseño de gramáticas independentes do contexto.
6. Deseño de gramáticas independentes do contexto e Forma Normal de Chomsky.
7. Deseño de autómatas con pila por estado final.
8. Deseño de autómatas con pila por baleirado de pila.
9. Lema de bombeo para linguaxes independentes do contexto.
10. Deseño de máquinas de Turing estándar (i).
11. Deseño de máquinas de Turing estándar (ii).
12. Deseño de gramáticas sensibles ao contexto (GSC) e gramáticas sen restricións (GSR).

A avaliación da materia realizarase en dúas partes: avaliación continua e exame final. Para aprobar a materia é imprescindible superar ámbalas dúas partes por separado.

A avaliación continua realizarase mediante a entrega dos boletíns de prácticas correspondentes a cada sesión, así como por medio de test con preguntas relativas aos boletíns entregados. Estes test realizaranse de forma presencial durante as clases de prácticas. O peso máximo dos boletíns de prácticas na avaliación continua será de 7 puntos. Ademais, ao longo do curso realizaranse exames parciais que permitirán sumar ata 3 puntos en total. A nota máxima que se pode obter na avaliación continua será de 10 puntos.

No exame final escrito o alumno poderá lograr un máximo de 10 puntos.

A nota final da materia será a media aritmética da avaliación continua e o exame final, excepto naquelas situacións nas que non se aprobase algunha das dúas partes, caso no que a nota final será o mínimo entre a avaliación continua e o exame final, debendo volver a avaiiarse segundo se indica posteriormente.

A entrega dalgún dos boletíns de prácticas ou dalgunha das probas de avaliación continua supoñerá que o alumno optou por presentarse á materia. Por tanto, a partir dese momento aínda non presentándose ao exame final terá consumida unha oportunidade.

Na segunda oportunidade (xullo) conservarase a nota da avaliación continua obtida durante o cuadrimestre, no caso de ter unha cualificación da mesma de 4 ou máis puntos, en cuxo caso a cualificación global será a media aritmética entre dita cualificación e a obtida no exame de teoría da segunda oportunidade. Noutro caso o estudante terá tamén que ser avaliado de novo da parte de prácticas da materia nesta segunda oportunidade.

No caso de realización fraudulenta de exercicios ou probas, será de aplicación o recollido na normativa de avaliación do rendemento académico dos estudantes e de revisión de cualificacións (https://www.xunta.gal/dog/Publicados/2011/20110721/AnuncioG2018-190711-…). En aplicación da normativa da ETSE sobre plaxio (aprobada pola Xunta da ETSE o 19/12/2019), a copia total ou parcial dalgún exercicio de prácticas ou teoría suporá o suspenso nas dúas oportunidades do curso, coa cualificación de 0,0 en ambos casos (https://www.usc.es/etse/files/u1/NormativaPlagioETSE2019.pdf).

A avaliación das competencias realizarase nas seguintes prácticas/exames:

[CE1] Todas as prácticas e exames.
[FB3, RI6, CE2] Prácticas, exames parciais e exame final.
[CG9, TR1] Todas as prácticas e exames.
[TR3] Todas as prácticas e exames.

O tempo de traballo do alumno na materia ao longo do curso desglósase do seguinte xeito:

(1) 25 horas de asistencia ás clases teóricas (2h/semana en xeral, con algunha excepción).

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

(3) 7,5 horas dedicadas á realización de actividades de avaliación (exames parciais e final).

(4) 85 horas de estudo autónomo e de realización de traballos e prácticas (5-6h/semana).

(5) 7,5 horas de avaliación de traballos e prácticas mediante test.

Recoméndase levar o estudo da teoría e a realización de prácticas e problemas ao día, xa que a avaliación mediante test así o require. Do mesmo xeito, considérase importante facer un uso intenso das titorías para a resolución de dúbidas.

Empregarase o Campus Virtual da USC como ferramenta de apoio ao proceso de aprendizaxe nos seguintes aspectos: respositorio de materiais (transparencias, exercicios, textos complementarios...), entrega e avaliación comentada de traballos obrigatorios e titorización virtual (correo electrónico e foros).

Para a realización de parte das prácticas empregarase o software JFLAP, que permite o deseño de autómatas e gramáticas, ou aplicar o lema de bombeo, entre outras funcionalidades.

A lingua predominante de impartición da materia será o galego.