1. Llenguatges
1.1. Conceptes fonamentals.
1.2. Relacions de Thue. Càlculs associatius.
1.3. Llenguatges formals. Operacions amb llenguatges.
1.4. Exemples i problemes.
2. Gramàtiques
2.1. Introducció.
2.2. Gramàtiques de Chomsky.
2.3. Gramàtiques lliures de context. (GLC) i Llenguatges lliures de context(LLC)
2.3.1. Arbres de derivació d’una GLC. Existència de LLCs inherentment ambigus.
2.3.2. Algorisme de simplificació de gramàtiques lliures de context.
2.3.3. Formes normals de les GLC. Forma normal de Chomsky i Forma normal de Greibach d’una GLC.
2.4. Gramàtiques regulars, llenguatges regulars i expressions regulars.
2.5. Exemples i problemes
3. Autòmats.
3.1. Autòmats finits deterministes. (AFD)
3.1.1. Formalització.
3.1.2. Exemples. autòmats unitaris, autòmats retardadors, autòmats sumadors i restadors binaris.
3.2. Autòmats com a reconeixedors.
3.3. Autòmats finits no deterministes (AFND). Equivalència entre AFD i AFND. Problema de trobar un AFD equivalent a un AFND donat.
3.4. AFND amb emoviments (eAFND). Equivalència entre AFND i eAFND. Problema de trobar un AFD equivalent a un AFND donat.
3.5. Simplificació d'autòmats.
3.6. Autòmats reconeixedors i expressions regulars. Teorema de Kleene.
3.7. Obtenció de l’expressió regular que representa el llenguatge acceptat per un autòmat.
3.8. Quan un llenguatge Žs regular i quan no ho es. Lema de bombejament per a llenguatges regulars. Exemples.
3.9. Exemples i exercicis.
3.10. Autòmats amb pila.(AP)
3.10.1. Definició i formalització.
3.10.2. Autòmats amb pila com a reconeixedors de llenguatges.
3.10.3. Autòmats amb pila deterministes i no deterministes.
3.10.4. Equivalència entre autòmats amb pila i llenguatges lliures de context.
3.10.5. Els autòmats amb pila com analitzadors sintàctics. Analitzadors LL(k) i LR(k).
3.10.6. Exemples i exercicis.
4. Models abstractes de càlcul
4.1. Preliminar
4.1.1. Llenguatges formals.
4.1.2. Jerarquia de Chomsky.
4.1.3. Enumerabilitat.
4.2. Calculabilitat I: Màquines de Turing
4.2.1. Model bàsic.
4.2.2. Disseny.
4.2.3. Models equivalents.
4.2.4. MT Universal
4.2.5. Llenguatges estructurats per frase.
4.2.6. Hipòtesi de Church.
4.3. Calculabilitat II: Models de Càlcul equivalents
4.3.1. Funcions Recursives.
4.3.2. Màquines RAMs.
4.3.3. Llenguatges de Programació Elemental.
4.3.4. Conclusions.
4.4. Indecidibilitat
4.4.1. Indecidibilitat en llenguatges.
4.4.2. Reduccions.
4.4.3. Teorema de Rice.
4.4.4. Indecidibilitat en llenguatges incontextuals.
4.5. Complexitat
4.5.1. Les classes P i NP.
4.5.2. La classe NP-Complet.
4.5.3. La classe co-NP.