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ÓNDE UNA GRAMÁ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
FORMANORMAL 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 DEESTUDIO
CAPÍTULO 3: MÁQUINAS DE ESTADO 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 GENERALESDEFINICIÓN FORMAL DE AUTÓMATA DE ESTADO FINITO
ASPECTOS 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 INTELIGENCIAARTIFICIAL
(ESPACIOS DE ESTADOS)
APLICACIONES EN INTELIGENCIA 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ÓMATADE PILA
DISEÑO DE AUTÓMATAS DE PILA
REPRESENTACIÓN ALTERNA DE UN AUTÓ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 problemaque se le presenta a un docente durante su práctica cotidiana es el
hecho de 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 acumplir con comisiones que les son asignadas, sufren de
enfermedades imprevistas 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 deotras organizaciones y empresas que
resintieron los efectos.
Esos hechos llevan a un 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...