Modulo de automatas y lenguajes formales

Solo disponible en BuenasTareas
  • Páginas : 162 (40279 palabras )
  • Descarga(s) : 0
  • Publicado : 27 de noviembre de 2010
Leer documento completo
Vista previa del texto
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., 2008

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.2008 Centro Nacional de Medios para el Aprendizaje

TABLA DE CONTENIDO.
Primera Unidad Capítulos 1. Conceptos Básicos I. LENGUAJES REGULARES Lecciones 1. Introducción e Historia. 2. Diferentes Modelos de Computación. 3. Autómatas y Lenguajes. 4. Lenguajes Regulares 5. Autómata 2. Autómatas Finitos 6. Definición Formal de Autómatas Finitos 7. Autómatas Finitos Determinísticos (AFD) 8. AutómatasFinitos no Determinísticos (AFND) 9. Autómatas Finitos con λ Transacciones 10. Lenguaje Aceptado por Autómata Finito 11.Expresiones Regulares 12. Significado de las Expresiones Regulares 13. Autómatas Finitos y Expresiones Regulares 14.Propiedades de los Lenguajes Regulares 15.Equivalencia de Autómatas Finitos Determinísticos y Autómatas Finitos no Determinísticos Lecciones 16. Gramáticas Regulares4. Conceptos Generales 17. Gramáticas Regulares y Lenguajes Regulares 18. Gramáticas Independientes del Contexto 19. Formas Canónicas para las Gramáticas Independientes del Contexto 20. Formas Norlmales 5. Autómatas a Pila II. LENGUAJES INDEPENDIENTES DEL CONTEXTO 21. Definición de Autómata con Pila 22. Diseño de Autómatas con Pila 23. Combinación Modular de Autómatas con Pila. 24. Autómatas conPila y Lenguajes Libres de Contexto 25. Relación entre los Autómatas de Pila y Lenguajes Libres de Contexto 26. Lema de Bombeo. 27. Propiedades de Clausura de los Lenguajes Libres de Contexto 28. Algoritmos de Decisión para los Lenguajes Libres de Contexto 29. Algoritmos de Pertenencia 30.Problemas Indecibles para Lenguajes Libres de Contexto

3. Expresiones Regulares

Segunda UnidadCapítulos

6. Propiedades de Lenguajes Independientes de Contexto

Tercera Unidad III. LENGUAJES ESTRUCTURADOS POR FRASES

Capítulos 31. Definición. 7. Máquinas de Turing. 32. Funcionamiento de la Máquina de Turing. 33. Diferencias entre un Computador y una Máquina de Turing 34. La Máquina Universal de Turing

35. Codificación de Máquinas de Turing

INTRODUCCIÓN
Autómatas y lenguajes formaleses 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áticas independientes del contexto y gramáticasgenerales), los tres tipos de máquinas 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 un papel secundario laimplementació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 lenguajes formales con reglas sintácticasy semánticas rígidas, concretas y bien definidas, de los lenguajes naturales como el inglés 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 construir las frases del lenguaje. Se...
tracking img