Enginyeria Tè;cnica en Informàtica de Sistemes (3372)

Teoria d'Autòmats i Llenguatges Formals I(12448) 

Objectius

L'objectiu d'aquesta assignatura es l'estudi formal de models matemàtics de sistemes digitals. Aquests models s'anomenen autòmats i ens permeten resoldre diferents tipus de problemes. Els models que estudiarem durant el curs son els autòmats finits, els autòmats finits amb sortida, els autòmats a pila i finalment les màquines de Turing. 

Tema 1. Autòmats finits i expressions regulars

Tema 2. Gramàtiques lliures de context

Tema 3. Autòmats a pila

Tema 4. Màquines de Turing

Tema 5. Indecidibilitat

Tema 6. Introducció a la teoria de la complexitat

Bibliografia bàsica

BORGES, QUIM & SERRA, JOAN & ARQUÉS, JOSEP M. Teoria d'autòmats, Col·lecció Materials, servei de publicacions de la U.A.B.
KELLEY, D.: Teoría de Autómatas y Lenguajes Formales, Prentice Hall, Madrid (1995). Hopcroft, J.E. & J.D. ULLMAN: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, (1979).
BROOKSHEAR, J.G. Teoría de la computación, Addison-Wesley Iberoamericana, Wilmingtond, Delaware (1993).
GABARRÓ VALLÈS, J. Informàtica Clàssica, Eumo Editorial, Vic (1995).