Trabajo

1. Lenguajes Regulares
1.1 Conceptos Basicos.
* Introducción
* Histórica
* Diferentes Modelos de Computación
* Autómatas y lenguajes
* Lenguajes regulares
* Autómata
1.2 Autómatas finitos
* Definición
* Autómatas finitos deterministicos.
* Autómatas finitos no deterministicos.
* Autómatas finitos con l Transacciones.
* Concepto de Autómatasfinitos no deterministas.
* Lenguajes aceptados.
1.3 Expresiones regulares.
* Significado de Expresión Regular.
* Autómatas finitos y Expresiones Teoremas de Equivalencia.
* Propiedades de lenguajes Regulares.
* AFN para la unión y concatenación.
* Equivalencia de autómatas.
* Introducción
* Los lenguajes pueden describirse como elementos que se generan,como cadenas a partir de cadenas sencillas, con el uso de operaciones de cadenas o el desarrollo del lenguaje mismo, que se puede generar con otros lenguajes más sencillos mediante operaciones de conjuntos.
* Los Lenguajes más sencillos son los considerados lenguajes regulares, es decir, los que se pueden generar a partir de lenguajes de un elemento con la aplicación de ciertas operacionesestandar realizadas un número finito de veces.
* Estos son pues los lenguajes que pueden reconocer los dispositivos llamados Autómatas finitos (AF) que son máquinas de cómputo con memoria muy restringida. En esta unidad se considera como segundo aspecto la idea de que un lenguaje no sea regular, ademas de proporcionar un modelo sencillo de computación que se puede generalizar en las unidadessiguientes.
* Con las caracterizaciones anteriores y otras de los lenguajes regulares se obtienen y estudian algoritmos para traducir una descripción de un lenguaje a otra descripción de un tipo distinto; se acumula experiencia en el uso de métodos formales para describir lenguajes y se intenta responder a preguntas acerca de ellos, son preguntas y ejercicios sencillos con sus respuestas y quepermiten determinar la utilidad de los lenguajes regulares en aplicaciones del mundo real .
* OBJETIVO GENERAL
* Reconocer los lenguajes regulares, autómatas finitos y su aplicación.
* OBJETIVOS ESPECIFICOS
* Estudiar la aplicación de los lenguajes regulares y los autómatas finitos.
* Adquirir las habilidades necesarias para desarrollar autómatas y máquinas que reconozcanlenguajes o computen funciones.
* Distinguir los diferentes tipos de lenguajes formales existentes.
*
Introducción
Los lenguajes se pueden clasificar según el tipo de dispositivos de aceptación y generación que existen para ellos. Estas clases corresponden a lenguajes de distinta complejidad que, a su vez, representan problemas de complejidad diferente. En particular se estudian dentrode todo el curso, las siguientes tres clases, las de la clásica jerarquía de Chomsky, además de algunas subclases de ellas: _ Lenguajes Regulares. _ Lenguajes Libres de Contexto. _ Lenguajes Enumerables Recursivamente o estructurados por frases. Para cada clase hay un tipo de dispositivo de aceptación para todas y solo las sentencias de esos lenguajes: autómatas de distinto grado de complejidad.También existe, para cada clase, un tipo de gramática que genera todas y sólo las sentencias de esos lenguajes. Los dispositivos de generación de los lenguajes regulares y de los lenguajes libres de contexto, son ampliamente usados como modelos para expresar la sintaxis de los lenguajes de programación. Sus mecanismos de aceptación forman la base para el diseño de los analizadores léxicos ysintácticos de los compiladores. En la actualidad, la aplicación de estas técnicas ha permitido que esas fases de los compiladores sean generadas en forma automática por programas que utilizan dichos modelos como base de trabajo. Las máquinas de Turing, dispositivos que aceptan y que también pueden generar los lenguajes enumerables recursivamente, fueron formuladas originalmente como un modelo de un...