Volver

Escuela Técnica Superior de Informática

Universidad Autónoma de Madrid

Teoría de autómatas y Lenguajes Formales

Resumen:

El curso tiene como objetivo dar una introduccion a los tres tipos fundamentales de mecanismos de definicion de lenguajes (expresiones regulares, gramaticas independientes del contexto y gramaticas generales), los tres tipos de maquinas correspondientes para su reconocimiento (automatas finitos, automatas a pila y maquinas de Turing) y las propiedades fundamentales de las familias de lenguajes por ellos definidas, incluyendo el estudio de condiciones necesarias para que un lenguaje sea de un tipo determinado.

El curso sirve de introduccion para el estudio de compiladores de lenguajes informaticos en la asignatura Procesadores de Lenguajes de tercer curso.

El curso es principalmente teorico, jugando un papel secundario la implementacion de algoritmos. Al final del curso el alumno debe demostrar la asimilacion de los conceptos fundamentales mediante la resolucion de problemas acerca de los mismos, asi como la realizacion de un reducido grupo de practicas en el ordenador.

1. Introducción
   Alfabetos, palabras y lenguajes.
   Operaciones sobre alfabetos, palabras y lenguajes.
   
   Concatenación
   Sustitución
   Expresiones regulares. Lenguajes regulares
   Gramáticas. Lenguajes secuencialmente enumerables.
   Gramáticas y lenguajes independientes del contexto.
   Análisis y ambigüedad.
2. Autómatas finitos y lenguajes regulares
   Autómatas finitos deterministas.
   Minimización de autómatas finitos deterministas.Autómata cociente.
   Autómatas finitos no deterministas. Equivalencia con los deterministas.
   Aceptación por autómatas finitos de lenguajes regulares.
   Propiedades de los lenguajes regulares.
   Lema de bombeo para lenguajes regulares.
    
3. Autómatas a pila y lenguajes independientes del contexto
   Autómatas a pila.
   Simplificación: formas normales.
   Aceptación de lenguajes independientes del contexto por autómatas a pila.
   Propiedades de los lenguajes independientes del contexto.
   Lema de bombeo para lenguajes independientes del contexto.
    
4. Máquinas de Turing y lenguajes recursivos y recursivamente enumerables
   Màquinas de Turing deterministas e indeterministas.
   Macros.
   Equivalencia.
   Aceptación de lenguajes recursivamente enumerables por máquinas de Turing.
   Propiedades de los lenguajes recursivamente enumerables.
    

Bibliografía

• Alfonseca, M., Sancho, J. y Martínez, M.: 'Teoría de lenguajes, gramáticas y Autómatas', Ed. Universidad y Cultura, Madrid, 1990
• Linz, P.: 'An introduction to Formal Languages and Automata', D.C. Heath and Co., Lexington, 1990