PDF de programación - Lenguajes Regulares

Lenguajes Regularesgráfica de visualizaciones

Actualizado el 21 de Marzo del 2018 (Publicado el 9 de Enero del 2018)
167 visualizaciones desde el 9 de Enero del 2018
178,0 KB
28 paginas
Creado hace 12a (01/10/2008)
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
  • Links de descarga
http://lwp-l.com/pdf8241

Comentarios de: Lenguajes Regulares (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad