control de lectura_capitulo 4 - Mauricio axel 20

Vista previa del material en texto

Lenguajes y autómatas 1 
INSTITUTO TECNOLÓGICO NACIONAL DE MÉXICO
INSTITUTO TECNOLÓGICO DE ACAPULCO
Ingeniería en sistemas computacionales
Lenguajes y autómatas 1
Control de lectura 
4.- Propiedades de los lenguajes regulares.
Profesor: Bedolla Solano Silvestre
López Anselmo Mauricio Axel 
CONTROL: 18320904
4.- Propiedades de los lenguajes regulares.
Ideas principales.
· Identificar las principales propiedades de los lenguajes regulares.
· Comprobar si un lenguaje es regular o no regular.
Resumen.
Una característica importante de los lenguajes regulares es la “propiedad de clausura”, que permite construir reconocedores para lenguajes que se han construido a partir de otros lenguajes mediante ciertas operaciones. Por ejemplo, la intersección de dos lenguajes regulares también es regular. Por tanto, dados autómatas que reconoce dos lenguajes regulares diferentes, podemos construir mecánicamente un autómata que reconozca exactamente la intersección de esos dos lenguajes. Dado que el autómata para la intersección puede tener muchos más estados que cualquiera de los dos autómatas dados, esta “propiedad de clausura” puede resultar ser una herramienta útil para construir autómatas complejos.
Otras propiedades importantes de los lenguajes regulares son las “propiedades de decisión”. El estudio de estas propiedades proporciona algoritmos que permiten responder a cuestiones importantes acerca de los autó-matas. Un ejemplo de esto es un algoritmo que permite decidir si dos autómatas definen el mismo lenguaje. Una consecuencia de esta capacidad de decidir acerca de esta cuestión es que podemos “minimizar” los autómatas, es decir, hallar un equivalente a un autómata dado que tenga el menor número posible de estados. Este problema ha sido importante en el diseño de circuitos de conmutación durante décadas, ya que el coste del circuito (área de un chip que ocupa el circuito) tiende a disminuir cuando el número de estados del autómata implementado por el circuito disminuye.
Estos teoremas a menudo se denominan propiedades de clausura de los lenguajes regulares, ya que demuestran que la clase de lenguajes regulares es cerrada respecto de la operación mencionada. Las propiedades de clausura expresan la idea de que cuando uno o varios lenguajes son regulares, entonces determinados lenguajes relacionados también lo son. Además, sirven como ilustración de cómo las representaciones equivalentes de los lenguajes regulares (autómatas y expresiones regulares) refuerzan entre si nuestra comprensión de la clase de lenguajes, ya que a menudo una representación resulta mucho mejor que las otras para demostrar una propiedad de clausura. A continuación, proporcionamos un resumen de las principales propiedades de clausura de los lenguajes regulares:
1. La unión de dos lenguajes regulares es regular.
2. La intersección de dos lenguajes regulares es regular.
3. El complementario de un lenguaje regular es regular.
4. La diferencia de dos lenguajes regulares es regular.
5. La reflexión de un lenguaje regular es regular.
6. La clausura (operador) de un lenguaje regular es regular.
7. La concatenación de lenguajes regulares es regular.
8. Un homomorfismo (sustitución de símbolos por cadenas) de un lenguaje regular es regular.
9. El homomorfismo inverso de un lenguaje regular es regular.
Síntesis
En este tema se abordarán diversos teoremas de los lenguajes regulares uno de estos será el “lema de bombeo” que nos dice lo siguiente:
Sea L un lenguaje regular. Existe entonces una constante (que depende de L) tal que para toda cadena w perteneciente a L con |w|≥n, podemos descomponer w en tres cadenas, w=XYZ
Otra característica importante de los lenguajes regulares es la propiedad de clausura, esta propiedad nos permite construir reconocedores para los lenguajes que se construyeron mediante otros lenguajes con ciertas operaciones.
Existen muchas operaciones que, cuando se aplican a los lenguajes regulares, proporcionan un lenguaje regular como resultado. Entre estas operaciones están la unión, la concatenación, la clausura, la intersección, la complementación, la diferencia, la reflexión, el homomorfismo (reemplazamiento de cada símbolo por una cadena asociada) y el homomorfismo inverso.
Bibliografías.
· Libro base-teoría de autómatas, lenguajes y computación-hopcroft
Página 1 | 1
Acapulco Gro. 09 de octubre de 2020