Universitat de Girona

Programa de l'assignatura

Curs 2003-04

3105200755 LLENGUATGES, GRAMÀTIQUES I AUTÒMATS


Objectius  
L'objectiu de l'assignatura consisteix en que l'alumne assoleixi els conceptes introductoris a la informàtica teòrica, generació de llenguatges via gramàtiques i reconeixement de llenguatges via autòmates. Alhora s'assoleix la base per l'assignatura de Models abstractes de càlcul.
 
Prerrequisits  
Obligatoris: cap
Recomanats: Introducció a la Lògica, Assignatures troncals de programació.
 
Contingut (Programa)  

1. Llenguatges i Gramàtiques

  1.1. Llenguatges Formals

  1.2. Gramàtiques Formals

2. Gramàtiques Regulars i Autòmats Finits

  2.1. Gramàtiques Regulars

  2.2. Autòmats Finits Deterministes

  2.3. Autòmats Finits No Deterministes

  2.4. Expressions Regulars

  2.5. Autòmats de cèl·lules

  2.6. Autòmats Probabilístics

3. Gramàtiques Independents del Context i Autòmats amb Pila

  3.1. Gramàtiques Independents del Context

  3.2. Autòmats amb Pila
 
Bibliografia  

Bibliografia bàsica a utilitzar durant el curs.

- JOHN E HOPCROFT, J.D. ULLMAN: "Introduction to automata theory, languages and computation", Addison-Wesley, (1979)
- GLENN BROOKSHEAR, J.: "Teoria de la computación: Lenguajes formales, autómatas y complejidad" Addison-Wesley Iberoamericana, (1993)
- GABARRÓ, J.: "Informàtica classica: autòmats i gramàtiques" Vic - Eumo (1995)
 
Mètodes docents  
(Mig quadrimestre)
Classes de teoria: 4 hores setmana
Problemes/Pràctiques: 2 hora setmana
 
Tipus d'exàmens i avaluacions  

Teoria: Prova final (0..10)
Problemes/Pràctiques: Treballs personals (A..E)
Nota final: Ponderació de teoria (75%) i laboratori (25%) (sempre i quan es superin ambdues parts). Més detalls a la corresponent Guia Docent ubicada a l'adreça del curs. 
 
Informació addicional  
 
Llengua de les classes  
Català