Enginyeria en Informàtica (3371)

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

Descripció

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 i els autòmats a pila aixi com altres models equivalents.

Objectius

L'objectiu de l'assignatura es que l'alumni conegui els diferentes models

formals de computacio del programa (autòmats finits deterministes, autòmats finits no deterministes, expressions regulars, autòmats a pila, gramàtiques lliures de context) a nivell intuitiu i formal.  

Temari

Tema 1. Autòmats finits

Tema 2. Expressions regulars

Tema 3. Autòmats a pila

Tema 4. Gramàtiques lliures de context

Pràctiques

Durant les sessions de pràctiques de l'assignatura es resoldran exercicis i problemes. No hi haura cap treball o pràctica a entregar.  

Mètode d'avaluació

La nota final de l'assignatura és la del examen. Les preguntes del examen cobriran tant questions teòriques com problemes.  

Bibliografia bàsica

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.

Hopcroft, J.E. , J.D. ULLMAN & R. MOTWANI : Introduction to Automata Theory, Languages and Computation, Addison-Wesley, (2000).

Bibliografia complementària

KELLEY, D.: Teoría de Autómatas y Lenguajes Formales, Prentice Hall, Madrid (1995). Hopcroft, J.E. & J.D.

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).