Teoría de Autómatas

• Temario
• Notas de curso
• Impartición en el cuatrimestre Ene-Abr del 2000

TEMARIO (Tentativo)

Descripción: Se hace una introducción matemática a los lenguajes formales y a los dispositivos lógicos necesarios para reconocerlos. Se ve la Jerarquía de Chomsky y la complejidad de los reconocedores sintácticos.

Temario:

INTRODUCCION A LA NOCION DE AUTOMATA

 

FUNDAMENTOS MATEMATICOS

Cadenas y lenguajes

Semigrupo de cadenas

Propiedades de lenguajes

GRAMATICAS FORMALES

Representación de lenguajes

Conceptos básicos de gramáticas

Gramáticas formales

Tipos de gamáticas

Arboles de derivación

Ambigüedad

 

MAQUINAS DE ESTADOS FINITOS

Máquinas de transición y con estados asignados

Conversión entre ambos tipos de máquinas

Equivalencia de máquinas de estados finitos

Reducción de estados

LENGUAJES DE ESTADOS FINITOS

Reconocedores de estados finitos

Reconocedores determinísticos e indeterminísticos y conversión entre ellos

Aplicaciones al diseño de máquinas

Reconocedores de estados finitos y su relación con las gramáticas regulares

Propiedades de los lenguajes de estados finitos

Ambigüedad

 

LIMITACIONES DE AUTOMATAS FINITOS

Limitaciones de reconocedores

Limitaciones de generadores

Limitaciones de traductores

 

AUTOMATAS DE CINTA

Reconocedores de cinta y gramáticas formales

Máquinas secuenciales generalizadas

Reconocedores de dos modos

Relación de reconocedores de estados finitos

 

AUTOMATAS DE PILA

Reconocedores de pila

Reconocedores de pila para gramáticas libres de contexto

Construcción de analizadores de sintaxis de pila

Propiedades de cerrado de los lenguajes libres de contexto

Reconocedores de pila determinísticos

Reconocedores de conteo

 

LENGUAJES LIBRES DE CONTEXTO

Introducción

Transformación de gramáticas

Formas canónicas de gramáticas

Estructura de los lenguajes libres de contexto

 

ANALISIS DE SINTAXIS

Análisis top-down y bottom-up

Análisis de precedencia

Análisis gereralizado de izquierda a derecha

 

MAQUINAS DE TURING

Conceptos fundamentales

Simulación de otros autómatas

Transductores de Turing

Reconocedores de Turing

Funciones computables y predicados

Algoritmos y computabilidad efectiva

Máquina universal de Turing

La bibliografía aquí presentada consiste de libros clásicos más que de libros "viejos".

Aho, Hopcroft, Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979

Denning, JB Dennis, JE Qualitz: Machines, languages and computation, Prentice-Hall, 1978

Ginzburg: Algebraic theory of automata, Academic Press, 1968

Harrison: Introduction to formal languages theory, Addison Wesley, 1978

Salomaa: Formal languages, Academic Press, 1973

Salomaa: Automata theory, Pergamon Press, 1969.

    Retorno al inicio de esta página

El libro  "Teoría de Autómatas", de Guillermo Morales-Luna, es el texto del curso. Está disponible en varios formatos: 1;2B PDF Comprimido, PostScript Comprimido, DVI y HTML.

Un cuadernillo de Mathematica para practicar con Autómatas Finitos está disponible para la versión 2.2 y para la versión 3.0. Es altamente recomendable que los interesados en este curso revisen también los cuadernillos de Mathematica, Algorithms on Finite Automata, del profesor Jaime Rangel Modragón.

    Retorno al inicio de esta página

En el período actual, estoy impartiendo este curso correspondiente al programa de Maestría en Ciencias con opción en Computación. La lista de los 14 estudiantes inscritos, enumerados según la enumeración para asignar tareas se puede ver aquí en PostScript. Los ejercicios y los programas serán asignados, a lo largo del curso, de manera consecutiva, módulo 14.

Programas

• Primera Lista (PS)

Ultima actualización: Febrero del 2000

    Retorno a la página "domicilio"