Lenguajes Regulares

Cap´
ıtulo 1
Alfabetos, cadenas y lenguajes
1.1.

Alfabetos y cadenas

Un alfabeto es un conjunto finito no vac´ cuyos elementos se llaman s´
ıo
ımbolos.
Denotamos un alfabeto arbitrario con la letra Σ.
Una cadena o palabra sobre un alfabeto Σ es cualquier sucesi´n finita de eleo
mentos de Σ. Admitimos la existencia de una unica cadena que no tiene s´
´
ımbolos,
la cual se denominacadena vac´ y se denota con λ. La cadena vac´ desempe˜a,
ıa
ıa
n
en la teor´ de lenguajes formales, un papel similar al que desempe˜a el conjunto
ıa
n
vac´ ∅ en la teor´ de conjuntos.
ıo
ıa
§

¤

§

¤

ımbolos a y b. Las
Ejemplo Sea Σ = {a, b} el alfabeto que consta de los dos s´
¦
¥siguientes son cadenas sobre Σ:
aba
ababaaa
aaaab.
Obs´rvese que aba = aab. El orden de loss´
e
ımbolos en una cadena es significativo
ya que las cadenas se definen como sucesiones, es decir, conjuntos secuencialmente
ordenados.
Ejemplo El alfabeto Σ = {0, 1} se conoce como alfabeto binario. Las cadenas
¦
¥sobre este alfabeto son secuencias finitas de ceros y unos, llamadas
secuencias binarias, tales como
001
1011
001000001.
§

¤

Ejemplo Σ = {a, b, c, . . . , x, y, z}, elalfabeto del idioma castellano. Las pala¦
¥bras oficiales del castellano (las que aparecen en el diccionario DRA)
son cadenas sobre Σ.
1

2

Teor´ de la Computaci´n
ıa
o

§

¤

2003-II

Profesor: Rodrigo De Castro

Ejemplo El alfabeto utilizado por muchos de los llamados lenguajes de progra¦
¥maci´n (como Pascal o C) es el conjunto de caracteres ASCII (o un
o
subconjunto de´l) que incluye, por lo general, las letras may´sculas y min´sculas,
e
u
u
los s´
ımbolos de puntuaci´n y los s´
o
ımbolos matem´ticos disponibles en los teclados
a
est´ndares.
a
El conjunto de todas las cadenas sobre un alfabeto Σ, incluyendo la cadena
vac´ se denota por Σ∗ .
ıa,

§

¤

¦

¥

Ejemplo

Sea Σ = {a, b, c}, entonces

Σ∗ = {λ, a, b, c, aa, ab, ac, ba, bb, bc,ca, cb, cc, aaa, aab, abc, baa, . . .}.
En la siguiente tabla aparecen las convenciones de notaci´n corrientemente utilio
zadas en la teor´ de lenguajes formales. De ser necesario, se emplean sub´
ıa
ındices.

Notaci´n usada en la teor´ de lenguajes
o
ıa
Σ, Γ

denotan alfabetos.

Σ∗

denota el conjunto de todas las cadenas que se pueden formar con los s´
ımbolos del alfabeto Σ.a, b, c, d, e,. . .

denotan s´
ımbolos de un alfabeto.

u, v, w, x, y, z, . . .
α, β, γ, . . .

denotan cadenas, es decir, sucesiones finitas de
s´
ımbolos de un alfabeto.

λ

denota la cadena vac´ es decir, la unica cadena
ıa,
´
que no tiene s´
ımbolos.

A, B, C, . . . , L, M, N ,. . . denotan lenguajes (definidos m´s adelante).
a
 Algunos autores denotan la cadena vac´ conla letra griega ε. Preferimos
ıa
denotarla con λ porque ε tiende a confundirse con el s´
ımbolo ∈ usado
para la relaci´n de pertenencia.
o
 Si bien un alfabeto Σ es un conjunto finito, Σ∗ es siempre un conjunto
infinito (enumerable). En el caso m´s simple, Σ contiene solo un s´
a
ımbolo,
Σ = {a}, y Σ∗ = {λ, a, aa, aaa, aaaa, aaaaa, . . .}.
 Hay que distinguir entre los siguientes cuatroobjetos, que son todos diferentes entre s´ ∅, λ, {∅} y {λ}.
ı:
 La mayor parte de la teor´ de lenguajes se hace con referencia a un
ıa
alfabeto Σ fijo (pero arbitrario).

Cap´
ıtulo 1

1.2.

Alfabetos, cadenas y lenguajes

3

Concatenaci´n de cadenas
o

Dado un alfabeto Σ y dos cadenas u, v ∈ Σ∗ , la concatenaci´n de u y v se
o
denota como u · v o simplemente uv y se definedescriptivamente as´
ı:
1. Si v = λ, entonces u · λ = λ · u = u. Es decir, la concatenaci´n de cualquier
o
cadena u con la cadena vac´ a izquierda o a derecha, es igual a u.
ıa,
2. Si u = a1 a2 · · · an , v = b1 b2 · · · bm , entonces
u · v = a1 a2 · · · an b 1 b 2 · · · b m .
Es decir, u · v es la cadena formada escribiendo los s´
ımbolos de u y a continuaci´n los s´
o
ımbolos de v....