Programa:

• Generalidades sobre lenguajes.
• Lenguajes y gramáticas. Jerarquía de Chomsky.
• Autómatas y lenguajes.
• Lenguajes regulares, autómatas finitos y expresiones regulares.

Objetivos pedagógicos:

Se pretende proporcionar al alumno de una visión de carácter básico sobre un área de encuentro de las matemáticas y las ciencias de la computación. Para ello se aborda un estudio introductorio, desde el punto de vista algebraico, de la teoría de autómatas y lenguajes formales. Estos tópicos son de interés en los contextos de la lógica formal, de la teoría de semigrupos y de las ciencias de la computación, así como en la interrelación entre ellos.

Bibliografía recomendada:

• Fountain, J. (ed.), Semigroups, formal languages and groups. Proceedings of the NATO Advanced Study Institute, York, UK, August 7--21, 1993. NATO ASI Series. Series C. Mathematical and Physical Sciences. 466. Dordrecht: Kluwer Academic Publishers. (1995).
• Howie, J.M., Autómata and Languages, Oxford Science Publications, Clarendon Press, Oxford, 1991.
• Rozenberg, G.(ed.); Salomaa, A.(ed.), Handbook of formal languages. Vol. 1-3. Berlin: Springer. (1997).
• Straubing, H., Finite Automata, Formal Logic and Circuit Complexity, Progress in Theoretical Computer Science, Birkhäuser, 1994.

Metodología:

En primer lugar se estudian los lenguajes formales a través del concepto algebraico de gramática. Se introducen los distintos tipos de lenguajes y gramáticas, según la jerarquía de Chomsky. A continuación se estudia el concepto de autómata o máquina abstracta como una estructura algebraica. Se establece seguidamente la conexión entre los distintos tipos de máquinas definidos y la clasificación de los lenguajes formales establecida previamente.
Seguidamente se centra la atención en los llamados lenguajes regulares, estableciendo en primer lugar su conexión con el concepto de autómata finito. Finalmente se aborda el estudio de este tipo de lenguajes desde el punto de vista de las expresiones regulares.

Criterios de evaluación:

Se valora la participación activa en las clases en particular mediante la realización de ejercicios propuestos. Elaboración y exposición de un trabajo final relacionado con los contenidos del curso. Eventual examen sobre la materia impartida.