Page 64 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

64

ENTREGA IV

LENGUAJES REGULARES Y NO REGULARES

1. Un criterio de regularidad
2. El lema de “bombeo” para lenguajes regulares

Problemas de decisión relativos a lenguajes regulares

Lenguajes regulares y no regulares:

Dijimos que los lenguajes regulares son aquellos que son reconocidos por autómatas finitos
deterministas y no deterministas y son aquellos lenguajes generados por gramáticas regulares, son
los representados por expresiones regulares.

Una expresión regular para un alfabeto ∑ se define como sigue:
 Ө es una expresión regular.

 Cada miembro de ∑ es una expresión regular.
 Si P y Q son expresiones regulares entonces también lo es (P ᴜ Q).

 Si P y Q son expresiones regulares entonces también lo es (P ᵒ Q).
 Si P es una expresión regular entonces también LO .
∗
En lo que lenguajes no regulares respecta, habría que considerar en su práctica de programación,
que no todas las veces un compilador encuentra el error que se atribuye a un número de paréntesis
derecho mayor o menor que el número de paréntesis izquierdo, por citar un ejemplo. Esto es así
porque para poder analizar esto correctamente el analizador léxico tendría que tener alguna forma
de recordar la cuenta que pudiera hacer y un AFD no tiene esta capacidad.

Existe un teorema que dice que si un lenguaje regular contiene cadenas de la forma para

enteros arbitrariamente grandes, entonces debe contener cadenas de la forma donde m y n

no son iguales. De aquí se deduce que el lenguaje no es regular ya que no puede aceptar

porque esto supone que el lenguaje aceptaría expresiones correctas como incorrectas.
Realmente hemos podido observar en la práctica que no todos los detalles de una estructura de
nuestros programas son reconocidos por el autómata finito, pero pueden reconocer muchas de las
estructuras que se analizan.

Un criterio de regularidad:
El lema de bombeo para lenguajes regulares enuncia una propiedad que cumplen todos los
lenguajes regulares infinitos (y también algunos lenguajes que no son 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, de manera estricta.

Enunciado del lema de bombeo (para lenguajes regulares)
“El lema de bombeo: se usa para demostrar que un lenguaje no es regular, es decir, que no
puede ser aceptado, ese lenguaje, por un autómata finito determinístico.”
Para todo lenguaje regular infinito L, existe una constante N, dependiente de ese lenguaje, de