Lenguajes Regulares
Antonio Falcó
- p. 1
Cadenas o palabras I
n Una cadena o palabra es una sucesión finita de símbolos.
u cadena {c, a, d, e, n}.
u 10001 {0, 1}
n El conjunto de símbolos que empleamos para construir las
cadenas o palabras se le llama alfabeto y lo denotaremos
genéricamente por Σ.
u Σ = {a, b, . . . , x, y, z} forma el alfabeto latino.
u Σ = {0, 1, 2, . . . , 9} forman el alfabeto númerico arábigo.
u Σ = {0, 1} forman el alfabeto binario.
n Una cadena o palabra sobre el alfabeto binario se le llama
cadena binaria.
n Se dice entonces que x es una cadena basada en el
alfabeto Σ si
donde xi ∈ Σ para i = 1, 2, . . . , n.
x = x1x2 · · · xn
- p. 2
Cadenas o palabras II
n Si x no contiene ningún símbolo del alfabeto, entonces
diremos que x es la cadena o palabra vacía y la
denotaremos por ε.
n Denotaremos la longitud de una cadena como
|x| =( n
0
si
si
x = x1x2 · · · xn
x = ε.
n Sean x = x1 · · · xn e y = y1 · · · ym. Diremos que x = y si
1. n = m y
2. xi = yi para i = 1, 2, . . . , n.
n Definimos la operación de concatenación como
en este caso
x y = x1 · · · xny1 · · · ym
|x y| = |x| + |y| = n + m.
- p. 3
Concatenación y Multiplicación
1. Existe un elemento neutro para la concatenación: la palabra
vacía.
2. Se cumple la propiedad asociativa de forma trivial
x ε = ε x = x.
(x y) z = x (y z) = x y z
3. No se cumple la propiedad conmutativa
01 10 6= 10 01
4. Existe el equivalente a la “matriz traspuesta”, la llamada
inversión de una cadena o palabra:
xR = (x1x2 · · · xn−1xn)R = xnxn−1 · · · x2x1.
5. Si xR = x se dice que la palabra es un palíndromo:
(01 10)R = 01 10.
- p. 4
Prefijos, sufijos y potencias
n Si x = y z diremos que y es un prefijo de la palabra x y z es
un sufijo de la misma palabra.
n Podemos escribir
teniendo en cuenta que
x x = x2
x1 = x.
n En general
n De forma evidente
xn =
x0 = ε.
n−veces
x · · · x
z }| {
- p. 5
Ejemplos en Σ = {0, 1}
n 14 = 1111.
n (10)3 = 10 10 10.
n ((10)3)R = (10 10 10)R = 010101.
n Resuelve la ecuación x 011 = 011 x.
u Es claro que x = ε resuelve el problema y que x = 011
tambien.
u Veamos que ocurre si consideramos soluciones del tipo
x = 011y. Entonces
011y 011 = 011 011y ⇒ y 011 = 011y,
el caso anterior nos dice que y = ε, 011 ⇒ x = 011, (011)2
u Veamos que ocurre si consideramos soluciones del tipo
x = y011. Entonces
y 011 011 = 011 y 011 ⇒ y 011 = 011y.
En general, x = (011)n, n ≥ 0.
- p. 6
Lenguajes
n Un lenguaje sobre un alfabeto Σ es cualquier conjunto
formado por cadenas o palabras sobre ese alfabeto.
u A = {ε, 0, 1, 00, 11, 01, 10} es un lenguaje sobre Σ = {0, 1}.
u A formado por las palabras palíndromos castellanos es
un lenguaje sobre el alfabeto latino.
n Si A y B son lenguajes entonces
A ∪ B = {x : x ∈ A o x ∈ B}
A ∩ B = {x : x ∈ A y x ∈ B}
A \ B = {x : x ∈ A y x /∈ B}
A · B = {x : x = y z, y ∈ A y z ∈ B}.
n−veces
An =
A · A · · · · · A, A0 = {ε}, A1 = A.
z
}|
{
- p. 7
Ejemplos
A = {0, 1, 00, 10}, y B = {ε, 00, 11}.
n A ∪ B = {0, 1, 00, 10, ε, 11}
n A ∩ B = {00}
n A \ B = {0, 1, 10}.
n A · B = {0, 000, 011, 1, 100, 111, 00, 0000, 0011, 10, 1000, 1011}
n A2 =
{00, 01, 000, 010, 10, 11, 100, 110, 001, 0000, 0010, 101, 1000, 1010}
Puede ocurir que
{0, 1, 10} ∩ {ε, 00, 11} = ∅,
Entonces a ∅ se le llama lenguaje vacío que es aquel que no
contiene ninguna palabra o cadena. No confundir con la
palabra vacía ε.
- p. 8
Clausura de Kleene
Dado un lenguaje A definimos su clausura de Kleene A∗
como:
A∗ = A0 ∪ A1 ∪ A2 ∪ · · · ∪ An ∪ · · · =
En particular
An.
∞
[n=0
{0, 1}∗ = {ε} ∪ {0, 1} ∪ {00, 01, 10, 11} ∪ · · ·
lo forman todas las cadenas binarias posibles (de cualquier
longitud) incluida la palabra vacía.
En consecuencia cualquier lenguaje binario está contenido en
la clausura de Kleene del alfabeto binario, esto es, en Σ∗
siendo Σ = {0, 1}.
n Si A es un lenguaje en el alfabeto Σ entonces A está
contenido en Σ∗.
- p. 9
Lenguaje complementario
Sea A un lenguaje sobre el alfabeto Σ.
n A = Σ∗ \ A = {x ∈ Σ∗ : x /∈ A}
n Ejemplo:Si
Σ = {0, 1}
entonces
A = {1} · Σ∗ = {1 x : x ∈ Σ∗},
está formado por todas las palabras que empiezan por 1. En
consecuencia A estará formado por todas las cadenas que
no empiezan por 1, y lo podemos escribir como
A = ({0} · Σ∗) ∪ {ε}.
- p. 10
Ejemplo
Describe el lenguaje
{0, 10}∗
n Aparte de la palabra vacía y el mismo nos encontramos con
{0, 10} ∪ {00, 010, 100, 1010} ∪ · · ·
Nos damos cuenta que siempre acaban en cero y que
nunca contiene dos unos seguidos. Nótese que si no
contiene unos entonces es de la forma 0n con n ≥ 0. Las
palabras de una longitud dada que contienen mayor número
de unos son de la forma (10)n.
Luego son palabras que nunca contienen la subcadena 11.
- p. 11
Ejemplo
Demuestra que dados dos lenguajes A y B se tiene
(A · B)R = BR · AR
n En este caso
(A · B)R = {(y z)R, y ∈ A y z ∈ B}
y
BR · AR = {zR yR, y ∈ A y z ∈ B}
n Hay que demostrar que para cualquier par de palabras y, z
se cumple que:
n Ahora
(y z)R = zR yR
(y1y2 · · · yn−1ynz1z2 · · · zm−1zm)R
= zmzm−1 · · · z2z1ynyn−1y2y1
= (zmzm−1 · · · z2z1)(ynyn−1 · · · y2y1)
= (z1z2 · · · zm−1zm)R(y1y2 · · · yn−1yn)R
- p. 12
Lema de Arden
Lema 1 Sean A y B dos lenguajes sobre un alfabeto Σ, de
forma que A no contiene la palabra vacía. Si X es un lenguaje
que cumple la relación
X = AX ∪ B,
Entonces X = A∗ · B.
- p. 13
Ecuaciones con lenguajes
Ejemplo 2 Si U y V son lenguajes sobre {a, b} y cumplen las
ecuaciones
U = {ε} ∪ {a} · U ∪ {b} · V
V = {ε} ∪ {b} · V
(1)
(2)
Encuentra una representación simple para U y V.
De (2) con X = V, A = {b} y B = {ε} obtenemos que
V = {b}∗ · {ε} = {b}∗
Sustituyendo en (1) obtenemos
B
U = {ε} ∪ {a} · U ∪ {b} · {b}∗, ⇒ U =
{ε} ∪ {b} · {b}∗ ∪
empleando de nuevo el Lema de Arden obtenemos
U = {a}∗ · ({ε} ∪ {b} · {b}∗) = {a}∗{b}∗.
z
}|
{
A
z}|{{a} ·U,
- p. 14
Reflexiones
Una forma de escribir las soluciones del problema anterior
sería escribir
y
V = b∗ ∪ ε = b∗
U = a∗(ε ∪ b b∗) = a∗b∗.
Llegamos a expresiones del tipo
A = aabb(ab∗ ∪ b)bb∗,
esto nos dice que las palabras de A son de la forma:
aabb(ε ∪ b)bb = aabb bb ∪ aabb b bb
Esto es el equivalente al comando de búsqueda
dir pepet*.*
identificamos todos los ficheros de estas caraterísticas con las
palabras de un lenguaje descrito mediante lo que se conoce
como una expresión regular.
- p. 15
Expresiones Regulares
Dado un alfabeto Σ defimos las expresiones regulares sobre el
mismo de la forma siguiente:
1. ∅ es una expresión regular que representa al lenguaje vacío.
2. ε es una expresión regular que representa al lenguaje {ε}.
3. Cada elemento a del alfabeto es una expresión regular que
representa al lenguaje {a}.
4. Si rA y rB son expresiones regulares que representan a los
lenguajes A y B, respectivamente, entonces
a) rA + rB que representa a A ∪ B
b) rArB que representa a A · B y
c) r∗
A que representa a A∗
son expresiones regulares.
5. No existen más expresiones regulares sobre Σ que no sea
una de estas.
- p. 16
Ejemplos
n
n
que representa
{a, b}∗ = (a + b)∗
({a} ∪ {b})∗.
a∗(ε ∪ b b∗) = a∗(ε + bb∗) = aε + abb∗ = a + abb∗.
n Describir en castellano el lenguaje que representa la
expresión regular siguiente:
a(a + b)∗.
En este caso cualquier palabra con el alfabeto {a, b} que
empieze por la letra a.
- p. 17
Preferencias en las operaciones
1. La clausura de Kleene tiene preferencia sobre la unión y la
concatenación.
2. La concatenación tiene preferencia sobre la unión.
3.
4.
r(s + t) = rs + st
(r + s)t = rt + st
Ejercicio 3 Demuestra que a∗(a + b)∗ = (a + ba∗)∗.
Definición 4 Denotaremos por r+ = r r∗.
- p. 18
Lenguajes regulares
Definición 5 Diremos que un lenguaje L sobre un alfabeto Σ
es regular si podemos construir una expresión regular r de
forma que L = r.
Ejemplo 6 {0, 1}∗ es un lenguaje regular ya que
{0, 1}∗ = (0 + 1)∗.
Ejemplo 7 Si L es un lenguaje regular sobre un alfabeto Σ.
Demostrar que el lenguaje
L′ = {w : u w está en L para alguna cadena u}
es regular.
- p. 19
Lema de Arden (revisitado)
Lema 8 Sean r y s dos expresiones regulares sobre un
alfabeto Σ, de forma que r no contiene la palabra vacía. Si x
es una expresión regular que cumple la relación
x = r x + s,
Entonces x = r∗ s.
Demostración. Hay que demostrar que x ⊂ r∗ s y que
r∗ s ⊂ x. Para ello empleamos inducción sobre la longitud de
|w| en x Si w = ε, entonces como r no contiene ε se tiene que
w = ε ∈ rx + s luego w ∈ s ⊂ r∗s. Supongamos que para
cualquier w en x de longitud n se cumple que w ∈ r∗s y
consideremos ahora una cadena w de longitud n + 1 como
w ∈ rx + s si w ∈ s ⊂ r∗s la propiedad se cumple, en caso
contrario tenemos w ∈ rx, luego w = rw′ con w′ de longitud
menor o igual a n. La hipótesis de inducción nos dice que
w′ ∈ r∗s, luego w = rw′ ∈ rr∗s ⊂ r∗s.
- p. 20
Lema de Arden (revisitado)
Lema 9 Sean r y s dos expresiones regulares sobre un
alfabeto Σ, de forma que r no contiene la palabra vacía. Si x
es una expresión regular que cumple la relación
x = r x + s,
Entonces x = r∗ s.
Demostración. Falta demostrar que r∗ s ⊂ x. Demostraremos
por inducción que rns ⊂ x para todo n ≥ 0. Para n = 0 se tiene
que probar que s ⊂ x, pero esto es evidente a partir de la
expresión x = r x + s. Supongamos que se cumple rks ⊂ x
para k ≤ n, en particular rn+1s = r(rns) ⊂ rx. Luego
rn+1s ⊂ rx ⊂ rx + s = x.
- p. 21
Principio de inducción generalizado
Deseamos demostrar que los lenguaje regulares cumplen una
propiedad Q
1. Demostrar que ∅ cumple la propiedad Q.
2. Demostrar que para cada a del alfabeto se cumple la
propiedad Q
3. Demostrar que si A y B cumplen la propiedad Q entonces
A ∪ B, A ∩ B y A∗ cumplen la propiedad Q.
- p. 22
Grafos y expresiones regulares
Nos gustaría representar una expresión regular cualquiera r
empleando un grafo dirigido y etiquetado.
Ejemplo 10 Consideremos la expresión regular
r = (11 + 0)∗(00 + 1)∗
Construyamos un grafo dirigido G(r) de forma que cualquier
cadena x del lenguaje rep
Crear cuenta
Comentarios de: Lenguajes Regulares (0)
No hay comentarios