CONTENIDOS DEL PRIMER CUATRIMESTRE DE
TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
§ Definiciones de la Teoría de Conjuntos (1.1)
§ Conjuntos Finitos e Infinitos (1.2)
§ Técnicas de Demostración
o Principio de Inducción (1.3)
§ Lenguajes
o Definiciones (2.1)
o Clasificación (2.7)
- Concepto de Representación (2.2 a 2.4)
- Definición de Gramática (2.5)
- Clasificación de Gramáticas (2.6)
o Preguntas básicas (2.8)
o Operaciones sobre lenguajes (3.1)
o Lema del Bombeo (8.2 y 11.1)
§ Gramáticas Regulares (4.1 y 4.2)
§ Expresiones Regulares (5.1 y 5.2)
§ Autómatas Finitos
o AFD (6.1)
o AFND (6.2)
o AFDM (6.4)
§ Equivalencia de modelos
o Propiedades de cierre (7.1)
§ Gramáticas de Contexto Libre
o FNC y FNG (9.4)
- GCL propia (9.3)
- GCL sin símbolos inútiles (9.3)
- GCL sin reglas unitarias (9.3)
- GCL no recursiva por la izquierda (9.2)
§
APND
(10.1)
o " M APND $ M’ APNDS / MºM’ (10.2)
o " M APNDS $ G GeCL / L(M)=L(G) (10.2)
o " G GeCL $ G’ GCL / L(G)=L(G’)-{e} (9.3)
§ Propiedades de cierre (9.5)