Automatas Lenguajes

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 ´unica cadena que no tiene s´ımbolos,

la cual se denomina cadena vac´ıa y se denota 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 6= aab. El orden de los s´ı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}, el alfabeto del idioma castellano. Las palabras oficiales del castellano (las que aparecen en el diccionario DRA)

son cadenas sobre Σ.

12 Teor´ıa de la Computaci´on 2003-II Profesor: Rodrigo De Castro

✞

✝

☎

✆

Ejemplo El alfabeto utilizado por muchos de los llamados lenguajes de programaci´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´ımbolos de 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 corrientemente utilizadas 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 finitas de

s´ımbolos de un alfabeto.

λ denota la cadena vac´ıa, es decir, la ´unica cadena

que no tiene s´ımbolos.

A, B, C, . . . , L, M, N,. . . denotan lenguajes (definidos m´as adelante).

✎ Algunos autores denotan la

...