Automatas

MODULO AUTÓMATAS Y LENGUAJES FORMALES

Edgar Alberto Quiroga Rojas

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD FACULTAD DE CIENCIAS BÁSICAS E INGENIERÍA PROGRAMA INGENIERIA DE SISTEMAS BOGOTÁ D.C., 2005

MODULO AUTÓMATAS Y LENGUAJES FORMALES @Copyright Universidad Nacional Abierta y a Distancia ISBN Autor: Edgar Alberto Quiroga Rojas Diseño Portada Juan Olegario Monroy V. 2005Centro Nacional de Medios para el Aprendizaje

TABLA DE CONTENIDO
UNIDADES DIDÁCTICAS Primera Unidad LENGUAJES REGULARES Capítulos Conceptos Basicos. Temas Introducción Introducción Histórica Diferentes Modelos de Computación Autómatas y lenguajes Lenguajes regulares Autómata Definición Autómatas finitos deterministicos. Autómatas finitos no deterministicos. Autómatas finitos con λ Transacciones.Concepto de Autómatas finitos no deterministas. Lenguajes aceptados. Significado de Expresión Regular. Autómatas finitos y Expresiones Teoremas de Equivalencia. AFN para la unión y concatenación. Equivalencia de autómatas. Temas Conceptos generales Arboles de derivación y ambigüedad Formas canónicas. Formas normales. Concepto de AP funcionamiento de AP. Diseño de AP Combinación Modular de AP AP yLenguajes Libres de contexto. Identificación de lenguajes independientes del contexto. Propiedades de cierre. Algoritmos de decisión. Temas

Autómatas finitos

Expresiones regulares. Propiedades de lenguajes regulares. Capítulos Gramáticas independientes del contexto. Autómatas a pila.

Segunda Unidad LENGUAJES INDEPENDIENTES DEL CONTEXTO

Tercera Unidad

Propiedades de lenguajesindependientes del contexto Capítulos

LENGUAJES ESTRUCTURADOS POR FRASES

Máquinas de Turing. Máquina de Turing y Computación. Funciones recursivas.

Conceptos generales, Otras definiciones. Funcionamiento de la MT. Tesis de Church/Turing. Máquina de Turing Universal. Funciones computables. Decidibilidad. Introducción Funciones recursivas primitivas Funciones recursivas parciales

INTRODUCCIÓNAutómatas y lenguajes formales es un curso de carácter teórico, que se inscribe en el campo de formación profesional básico del Programa de Ingeniería de Sistemas con un valor académico de tres créditos. El estudiante en el desarrollo de este curso demuestra la asimilación de los conceptos y mecanismos fundamentales para la definición de lenguajes (expresiones regulares, gramáticasindependientes del contexto y gramáticas generales), los tres tipos de maquinas correspondientes para su reconocimiento (autómatas finitos, autómatas a pila y maquinas de Turing) y las propiedades fundamentales de las familias de lenguajes por ellos definidas, también realiza el estudio de las condiciones necesarias para que un lenguaje sea de un tipo determinado. El curso es principalmente teórico, jugando unpapel secundario la implementación de algoritmos. Al final del curso el estudiante debe demostrar la asimilación de los conceptos fundamentales mediante la resolución de problemas acerca de los mismos, así como la realización de algunas prácticas en el computador. Este curso toma como base el avance de los lenguajes de programación de alto y bajo nivel para propiciar la distinción entre lenguajesformales con reglas sintácticas y semánticas rígidas, concretas y bien definidas de los lenguajes naturales, como el ingles o el español, donde la sintaxis y la semántica no se pueden controlar fácilmente. Los intentos de formalizar los lenguajes naturales, lleva a la construcción de gramáticas, como una forma de describir estos lenguajes, utilizando para ello reglas de producción para construirlas frases del lenguaje. Se puede entonces caracterizar un lenguaje mediante las reglas de una gramática adecuada. Los temas sobre autómatas, computabilidad, e incluso la complejidad algorítmica fueron incorporándose al currículo de ciencias de la computación de diferentes universidades desde la década de los 60, esta incorporación puso de manifiesto que las ciencias de la computación habían...