Cap1

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

Alfabetos y cadenas

Un alfabeto es un conjunto finito no vac´ıo cuyos elementos se llaman s´ımbolos.
Denotamos un alfabeto arbitrario con la letra Σ.
Una cadena o palabra sobre un alfabeto Σ es cualquier sucesi´on 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 sedenota con λ. La cadena vac´ıa desempe˜
na,
en la teor´ıa de lenguajes formales, un papel similar al que desempe˜
na el conjunto
vac´ıo ∅ en la teor´ıa de conjuntos.
✞

☎

✞

☎

Ejemplo Sea Σ = {a, b} el alfabeto que consta de los dos s´ımbolos a y b. Las
✝
✆siguientes son cadenas sobre Σ:
aba
ababaaa
aaaab.
Obs´ervese que aba = aab. El orden de los s´ımbolos en una cadena es significativo
ya quelas 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}, el alfabeto del idioma castellano. Las pala✝
✆bras oficiales delcastellano (las que aparecen en el diccionario DRA)
son cadenas sobre Σ.
1

2

Teor´ıa de la Computaci´on

✞

☎

2003-II

Profesor: Rodrigo De Castro

Ejemplo El alfabeto utilizado por muchos de los llamados lenguajes de progra✝
✆maci´
on (como Pascal o C) es el conjunto de caracteres ASCII (o un
subconjunto de ´el) que incluye, por lo general, las letras may´
usculas y min´
usculas,
los s´ımbolosde puntuaci´on y los s´ımbolos matem´aticos disponibles en los teclados
est´andares.
El conjunto de todas las cadenas sobre un alfabeto Σ, incluyendo la cadena
vac´ıa, se denota por Σ∗ .

✞

☎

✝

✆

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´on corrientementeutilizadas en la teor´ıa de lenguajes formales. De ser necesario, se emplean sub´ındices.

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

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 finitasde
s´ımbolos de un alfabeto.

λ

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

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

Cap´ıtulo1

1.2.

Alfabetos, cadenas y lenguajes

3

Concatenaci´
on de cadenas

Dado un alfabeto Σ y dos cadenas u, v ∈ Σ∗ , la concatenaci´
on de u y v se
denota como u · v o simplemente uv y se define descriptivamente as´ı:
1. Si v = λ, entonces u · λ = λ · u = u. Es decir, la concatenaci´on de cualquier
cadena u con la cadena vac´ıa, a izquierda o a derecha, es igual a u.
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´on los s´ımbolos de v.
La concatenaci´on de cadenas se puede definir inductiva o recursivamente de la
siguiente manera. Si u, v ∈ Σ∗ , a ∈ Σ, entonces
1. u · λ = λ · u = u.
2. u · (va) = (u · v)a.
Propiedad. La concatenaci´on de cadenas es una...