automatas

Lenguajes Regulares

Un alfabeto es un conjunto finito no vac´ıo cuyos elementos se llaman s´ımbolos.
Denotamos un alfabeto con la letra .
Una cadena o palabra sobre un alfabeto
es cualquier sucesi´on (o secuencia) finita de
elementos de . Admitimos la existencia de una u
´nica cadena que no tiene s´ımbolos,
la cual se denomina cadena vac´ıa y se denota por λ.
El conjunto de todas lascadenas sobre un alfabeto Σ, incluyendo la cadena vac´ıa, se
denota por Σ∗ . Si bien un alfabeto Σ es un conjunto finito, Σ∗ siempre es un conjunto
infinito (enumerable). En el caso m´as simple, Σ = {a} y Σ∗ = {λ, a, aa, aaa, aaaa, . . .}
Dado un alfabeto Σ y dos cadenas u, v ∈ Σ, la concatenaci´
on de u y v se denota
como uv y se define descriptivamente as´ı:
(1) Si v = λ, entonces uλ = λu =u.
(2) Si u = a1 a2 . . . an y v = b1 b2 . . . bm , entonces
uv = a1 a2 . . . an b1 b2 . . . bm
∗

Un lenguaje L sobre un alfabeto
es un subconjunto de
(puede ser finito
o infinito). Si A y B son lenguajes sobre
, entonces los siguientes tambi´en son
lenguajes sobre Σ:
A∪B

Uni´on

A∩B

Intersecci´on

A−B

Diferencia
∗

A=Σ −A

Complemento

AB = {uv : u ∈ A, v ∈ B}Concatenaci´on

Dado un lenguaje A sobre Σ, (A ⊆ Σ∗ ) y un n´
umero natural n ∈ N, se define An de
la siguiente forma
A0 = λ
An = AA · · · A = {u1 u2 · · · un : ui ∈ A, para todo i, 1 ≤ i ≤ n},
n veces

1

De esta forma, A2 es el conjunto de las concatenaciones dobles de cadenas de A, A3
est´
a formado por las concatenaciones triples y, en general, An es el conjunto de todas
lasconcatenaciones de n cadenas de A, de todas las formas posibles.
La clausura de Kleene o estrella de Kleene de un lenguaje A, es la uni´on de
todas las potencias de A y se denota por A∗ .
A∗ =

Ai = A0 ∪ A1 ∪ A2 · · · ∪ An · · ·
i≥0

Seg´
un la definici´
on de las potencias de un lenguaje, A∗ consta de todas las concatenaciones de cadenas de A consigo mismas, de todas las formas posibles.A∗ = {λ} ∪ {u1 u2 · · · un : ui ∈ A, n ≥ 1}
De manera similar se define la clausura positiva de un lenguaje A, denotado por
A+ .
A+ =

Ai = A1 ∪ A2 · · · ∪ An · · ·
i≥1

A+ se puede describir de la siguiente manera
A∗ = {u1 u2 · · · un : ui ∈ A, n ≥ 1}
Los lenguajes regulares sobre un alfabeto dado Σ son todos los lenguaje que se
pueden formar a partir de los lenguajes b´asicos ∅, {λ} y{a}, tal que a ∈ Σ, por medio
de las operaciones de uni´
on, concatenaci´on y estrella de Kleene.
A continuaci´
on presentamos una definici´on recursiva de los lenguajes regulares. Sea
Σ un alfabeto.
1. ∅, {λ} y {a}, para cada a ∈ Σ, son lenguajes regulares sobre Σ. Estos son los
denominados lenguajes regulares b´asicos.
2. Si A y B son lenguajes regulares sobre Σ, tambi´en lo son

A∪B
ABA

∗

Uni´on
Concatenaci´on
Estrella de Kleene

Observe que Σ, Σ∗ y todo lenguaje finito son lenguajes regulares sobre Σ. La uni´on,
la concatenaci´
on y la estrella de Kleene se denominan operaciones re-gulares.
Ejercicio 1.

Sea A y B lenguajes sobre Σ. Muestre las siguientes igualdades.

1. A+ = A∗ A = AA∗
2. A∗ A∗ = A∗
3. (A∗ )n = A∗
4. (A∗ )∗ = A∗
5. A+ A+ ⊆ A+
6. (A ∪B)∗ = (A∗ B ∗ )∗

Expresiones Regulares
Con el prop´
osito de simplificar la descripci´on de lenguajes regulares se definen las
expresiones regulares. A continuaci´on presentamos una definici´on recursiva
1. Expresiones regulares b´asicas:
∅ es una expresi´
on regular que representa el lenguaje {∅}.
λ es una expresi´
on regular que representa el lenguaje {λ}.
a es una expresi´
onregular que representa el lenguaje {a}, a ∈ Σ.
2. Si R y S son expresiones regulares sobre Σ, tambi´en lo son:
(R ∪ S)
(R)(S)
(R)∗

Ejemplo 1. Encontrar expresiones regulares que representen los siguientes lenguajes, definidos sobre el alfabeto Σ dado.
1. Σ = {0, 1}. Lenguaje de todas las cadenas que comienzan con el s´ımbolo 0 y
terminan con el s´ımbolo 1.
0(0 ∪ 1)∗ 1
2. Σ = {0, 1}....