• Author / Uploaded
• Julio Campos

Citation preview

Lenguajes regulares y no regulares Un lenguaje regular es un tipo de lenguaje formal que satisface las siguientes propiedades: Los lenguajes más sencillos que se considerarán son los lenguajes regulares, es decir, los que se pueden generar a partir de los lenguajes básicos, con la aplicación de las operaciones de unión, concatenación y * de Kleene un número finito de veces. Puede ser reconocido por:     

un autómata finito determinista un autómata finito no determinista un autómata de pila un autómata finito alterno una máquina de Turing de solo lectura

Lenguajes no regulares Todos los lenguajes no son regulares, simplemente hay que tener en cuenta que los lenguajes regulares son definidos por una expresión, cuando la intuición nos dice que se pueden definir lenguajes de una forma más compleja. No hay ningún método que nos permita decidir si un lenguaje es regular o no, ya que depende de la descripción del lenguaje. Aunque sí que tenemos diferentes herramientas que permiten probar que lenguajes específicos no son regulares.

El lema de bombeo para lenguajes no regulares Gracias a este lema podremos demostrar que ciertos lenguajes infinitos no son regulares. Es importante hacer notar que el lema de bombeo es una herramienta adecuada para demostrar que un lenguaje no es regular, pero no lo será para demostrar que un lenguaje si es regular (por el hecho de que existen algunos lenguajes no regulares que la cumplen). Por tanto, si un lenguaje no cumple el lema de bombeo no es regular, pero si lo cumple no podremos decir si es o no regular.

Enunciado del Lema de Bombeo Para todo lenguaje regular infinito L, existe una constante n, dependiente de ese lenguaje, de forma que si w es una cadena de L con ¦w¦ ≥ n, podemos partir w en tres cadenas, x, y, z, de forma que:

• w = xyz, • y ≠ ε (o dicho de otro modo, que ¦y¦ ≥ 1), • ¦xy¦