Teoria De La Computacion

CONTENIDO
PRÓLOGO COMENTARIOS PRELIMINARES CAPÍTULO 1: GRAMÁTICAS Y LENGUAJES FORMALES CONCEPTOS INTRODUCTORIOS CONCEPTOS IMPORTANTES NOMENCLATURA SIMPLIFICADA PARA CADENAS PREFIJOS, INFIJOS Y POSFIJOS (SUFIJOS) CONCATENACIÓN DE CADENAS OPERACIONES SOBRE LENGUAJES JERARQUÍA DE OPERADORES DE LENGUAJES DESCRIPCIÓN FORMAL DE LA GRAMÁTICA FORMAL GRAMÁTICA MAL ESTRUCTURADA CARACTERIZACIÓN DE UNAGRAMÁTICA DISEÑO DE GRAMÁTICAS FORMALES GRAMÁTICAS EQUIVALENTES GRAMÁTICAS CON LAMBDA O DECIDIBLES JERARQUÍA DE CHOMSKY GRAMÁTICA SIN RESTRICCIONES (TIPO 0) GRAMÁTICA SENSIBLE AL CONTEXTO (TIPO 1) GRAMÁTICA LIBRE DE CONTEXTO (TIPO 2) GRAMÁTICA REGULAR (TIPO 3) DERIVACIÓN POR LA IZQUIERDA Y POR LA DERECHA COMENTARIO FINAL SOBRE LOS TIPOS DE GRAMÁTICAS PROBLEMAS ADICIONALES FORMA NORMAL DE CHOMSKY (CNF)TRANSFORMACIÓN DE UNA GRAMÁTICA A LA CNF

Página 1

CAPÍTULO 2: LAS GRAMÁTICAS FORMALES EN LA COMPUTACIÓN FORMA NORMAL DE BACKUS - NAUR (BNF) ÁRBOLES DE DERIVACIÓN GRAMÁTICAS AMBIGUAS Y UNÍVOCAS REGLAS DE LENGUAJES DE PROGRAMACIÓN PARA OPERADORES ASOCIATIVOS POR DERECHA E IZQUIERDA APLICACIÓN DE LOS ANALIZADORES DE LENGUAJES TEORÍA DE COMPILADORES CASO DE ESTUDIO CAPÍTULO 3: MÁQUINAS DEESTADO FINITO DEFINICIÓN FORMAL DESCRIPCIÓN DE LA MÁQUINA DE ESTADO FINITO EJEMPLOS DE APLICACIONES DE MÁQUINAS DE ESTADO FINITO DIAGRAMA DE TRANSICIÓN DE LA MÁQUINA DE ESTADO FINITO TABLA DE TRANSICIÓN DE LA MÁQUINA DE ESTADO FINITO EJEMPLO: CONTADOR SÍNCRONO DE 3 BITS CONCEPTOS ADICIONALES CAPÍTULO 4: AUTÓMATAS DE ESTADO FINITO CONCEPTOS GENERALES DEFINICIÓN FORMAL DE AUTÓMATA DE ESTADO FINITOASPECTOS IMPORTANTES EN DISEÑO DE UN AUTÓMATA FINITO AUTÓMATAS EQUIVALENTES IMPLEMENTACIÓN DE UN AUTÓMATA FINITO APLICACIONES DE LOS AUTÓMATAS DE ESTADO FINITO SIMULACIÓN DE UN MODELO DEL MUNDO REAL (MÁQUINA PARA VENTA DE REFRESCOS) APLICACIONES EN CIRCUITOS DIGITALES SECUENCIALES (RECONOCEDOR DE IMPARIDAD DE PULSOS) APLICACIONES EN INTELIGENCIA ARTIFICIAL (ESPACIOS DE ESTADOS) APLICACIONES ENINTELIGENCIA ARTIFICIAL

Página 2

(REDES NEURONALES) AUTÓMATA FINITO DETERMINISTA (AFD) AUTÓMATA FINITO NO DETERMINISTA (AFND) RELACIÓN ENTRE AUTÓMATAS Y GRAMÁTICAS CONVERSIÓN DE UN AFND EN UN AFD AUTÓMATAS PARA EXPRESIONES REGULARES COMENTARIOS ADICIONALES CAPÍTULO 5: AUTÓMATAS DE PILA DESCRIPCIÓN GENERAL DEFINICIÓN FORMAL DEL AUTÓMATA DE PILA DISEÑO DE AUTÓMATAS DE PILA REPRESENTACIÓN ALTERNA DE UNAUTÓMATA DE PILA APÉNDICES 1. EL PROBLEMA DE LA FALTA DE CREATIVIDAD EN EL ESTUDIANTE DE MATEMÁTICAS___________________________________________________ 2. PROGRAMA VIGENTE DE LA ASIGNATURA CC209 (TEORÍA DE LA COMPUTACIÓN)____________________ 3. PROBLEMAS PROPUESTOS PARA RESOLVER EN CLASE

Página 3

PRÓLOGO
Un problema que se le presenta a un docente durante su práctica cotidiana es el hechode tener que enfrentar los imprevistos que pueden surgir durante el transcurso de un ciclo regular y que le puede causar el incumplimiento para sus estudiantes de los objetivos previstos en el programa oficial de la asignatura. En ocasiones los docentes asisten a sesiones de trabajo convocados por sus academias, acuden a cumplir con comisiones que les son asignadas, sufren de enfermedadesimprevistas o de diversas eventualidades. Además existen sucesos inesperados como ocurrió en el año 2009 cuando la sociedad mexicana fue afectada por el embate de la epidemia de una enfermedad que se denominó AH1N1 y que ocasionó la suspensión de actividades durante algunas semanas en las instituciones educativas, además de otras organizaciones y empresas que resintieron los efectos. Esos hechos llevan aun profesor a elaborar el presente texto oficial y elaborado a la medida para el curso de Teoría de la Computación que se imparte en el Centro Universitario de Ciencias Exactas e Ingenierías de la Universidad de Guadalajara. Cubre los temas que se estudian en las clases ordinarias de manera teórica y contiene varios problemas resueltos, para que el alumno con las bases adquiridas resuelva...