2018_19
Guia docent 
Escola Tècnica Superior d'Enginyeria
A A A 
català 
Doble titulació de Grau d'Enginyeria Informàtica i de Biotecnologia (2014)
 Assignatures
  LLENGUATGES FORMALS
   Continguts
Tema Subtema
1. Introducció 1.1. Els llenguatges de programació com a llenguatges formals.
1.2. Nocions bàsiques de llenguatges formals: definició, descripció, i reconeixement de llenguatges formals.
1.3. Estructura bàsica d'un compilador.
2. Llenguatges regulars 2.1. Expressions regulars.
2.2. Autòmats finits: deterministes, no deterministes i amb lambda-moviments.
2.3. Equivalència entre expressions regulars i autòmats finits.
2.4. Generadors d'analitzadors lèxics: flex.
3. Llenguatges independents del context 3.1. Gramàtiques independents del context.
3.2. Autòmats de pila.
3.3. Equivalència entre gramàtiques independents del context i autòmats de pila.
3.4. Generadors d'analitzadors sintàctics: bison.
4. Altres llenguatges formals 4.1. Classificació dels llenguatges formals: jerarquia de Chomsky.
4.2. Màquines de Turing.
4.3. Llenguatges recursius i llenguatges recursivament enumerables.
5. Calculabilitat i complexitat 5.1. Tesi de Church-Turing.
5.2. Màquina de Turing universal.
5.3. Problemes indecidibles: problema de l'aturada.
5.4. Introducció a la teoria de la complexitat.
5.5. Els problemes P, NP i NP-complets.
6. Processadors de llenguatges formals 6.1. Taula de símbols.
6.2. Anàlisi lèxica.
6.3. Anàlisi sintàctica.
6.4. Anàlisi semàntica.
6.5. Generació de codi intermedi.
6.6. Generació de codi objecte.