Estudia

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

1. 1. Llenguatges i Gramàtiques

2. 1.1. Llenguatges Formals

3. 1.2. Gramàtiques Formals

4. 2. Gramàtiques Regulars i Autòmats Finits

5. 2.1. Gramàtiques Regulars

6. 2.2. Autòmats Finits Deterministes

7. 2.3. Autòmats Finits No Deterministes

8. 2.4. Expressions Regulars

9. 2.5. Autòmats de cèl·lules

10. 2.6. Autòmats Probabilístics

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

12. 3.1. Gramàtiques Independents del Context

13. 3.2. Autòmats amb Pila

• P. Isasi, P. Martinez, D. Borrajo (1997). Lenguages, Gramaticas y Automatas. Un enfoque practico.. Addison-Wesley.
• JG Brookshear (1979). Teoria de la computacion. Addison-Wesley.
• JE Hopcroft, R. Motwani, KD Ullman (2001). Introduccion a la teoria de automatas, lenguajes, y computacion.. Addison-Wesley.

Activitats d'avaluació:

Mètodes docents:
(Mig quadrimestre: Inici curs -> Fires Girona)
Classes de teoria: 4 hores setmana
Problemes/Pràctiques: 2 hora setmana
Tipus d'exàmen:
Prova final (0..10) sobre els conceptes teòrics (80%) i s'inclourà com a mínim un exercici de la llista a resoldre durant l'assignatura (20%).

Prerequisits:
Obligatoris: cap
Recomanats: Introducció a la Lògica, Assignatures troncals de programació.

• LLENGUATGES, GRAMÀTIQUES I AUTÒMATES
• Matemàtica discreta
• Models abstractes de càlcul