Tema3 EXPRESIONES REGULARES

Teoría de la Computación para Ingeniería de Sistemas: un
enfoque práctico

Hilda Contreras
26 de marzo de 2012

2

Índice general
0.1. Propiedades cerradas y algoritmos de decisión . . . . . . . . . .
0.1.1. Lema del Bombeo o Potencias para Conjuntos Regulares
0.1.2. Propiedades de clausura de los Lenguajes regulares . . .
0.1.3. Algoritmos de decisión sobre conjuntos regulares . . . .
0.1.4.Preguntas y respuestas, ejercicios resueltos y propuestos
0.1.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

3
3
5
10
15

Propiedades cerradas y algoritmos de decisión

No todos los lenguajes son regulares y las herramientas para trabajar (reconocer, expresar y
generar) sobre los lenguajes regulares estan limitadas por el número nito de estadoso de clases
de equivalencia. Por lo que un lenguaje no regular (tipo 2 al tipo 0) no tiene la posibilidad
de modelarse efectivamente con herramientas regulares (AF y ER), y por tanto se necesita
identicar el tipo de lenguaje para determinar su solución (el modelo). Este tema pretende
mostrar características y propiedades para identicar cuando un lenguaje es o no regular.
0.1.1.

Lema del Bombeoo Potencias para Conjuntos Regulares

Es un método para demostrar que ciertos lenguajes NO son regulares. Si L es regular y M
= (Q,Σ,δ ,q0 ,F) es un AFD y L = L(M) con cierto número de estados n.
Consideremos a1 , a2 , ...am , m ≥ n (m símbolos) y sea δ(qo , a1 a2 ...ai ) = qi para i = 1,2,...,m (necesariamente se pasa por un estado 2 o más veces). No es posible que todos los qi sean distintos
yaque solo hay n estados. Por lo tanto hay 2 enteros j y k, tal que 0 ≤ j < k ≤ m, si qm está
en F, entonces a1 , a2 , ...am esta en L(M) pero también lo está a1 , a2 , ...aj (aj+1 ...ak )i ak+1 ...am
con i ≥ 0, i es el número de veces que se repite el ciclo o lazo de qj a qk como muestra la gura
1 (es decir, se concatena i veces la subcadena aj+1 ...ak y la cadena resultante sigue estando en
ellenguaje)

Teorema 1.

:

Si L es un conjunto regular entonces hay una constante
n tal que para w en L y |w| ≥ n podemos escribir w = xyz tal que:
Lema del Bombeo

1. y ̸= λ o |y| ≥ 1, la cadena a bombear y no es vacia, al menos tiene un símbolo.
2. |xy| ≤ n, el tamaño del prejo xy de w no es más grande que n

Bombear signica repetir i veces la concatenación de una cadena, generalmente seindica el bombeo con el
exponente de la potencia de la subcadena, por ejemplo a3 = aaa

3

4

ÍNDICE GENERAL

Figura 1: Bombeando la cadena wi = xy i z

3. Para todo i entero, xy i z pertenece a L, para cualquier valor entero mayor o igual al cero
la cadena bombeada sigue perteneciendo al lenguaje.
Es decir, siempre es posible encontrar una cadena no vacia y, no demasiado lejos del comienzo de w quese pueda "bombear"(repetir i veces) y la cadena resultante pertenece también
al lenguaje L.
Se debe usar el lema para demostrar por contradicción que un Lenguaje L no es regular, de la
siguiente forma:
1. Asumo que L es regular
2. Seleccionar un w adecuado que cumpla con las condiciones del lema (1 y 2) y que pertenezca a L (el lenguaje debe depender del valor n, constante del Lema).
3. Bombear ysalir de L (conseguir una contradicción para la condición 3 del lema, es decir
encontrar un solo valor de i para bombear la cadena y sacar el resultado del lenguaje L).
4. Al tener la contradicción, deducir que lo que se asume al principio es falso, por tanto el
lenguaje L no es regular.
Nota: el x,y,z no son jos, ni tienen longitudes jas sólo están limitados por las condiciones (1
y 2) del lemay la denición del lenguaje.
Ejemplos: Dados los siguientes lenguajes desmostrar si son o no lenguajes regulares
L = { 0j 1j | j ≥ 0 }
Se asume que L es un Lenguaje Regular, y se aplica el Lema del Bombeo. Se selecciona
w = 0n 1n , que cumple con que w = xyz, |w| ≥ n y |xy| ≤ n
Se va a bombear la cadena y que esta en 0n por las condiciones del Lema, cumpliendo
con la siguiente desigualdad 1 ≤...