Autómatas

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 denomina cadena vac´ yse 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 los s´ e ı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¦ ¥brasoficiales 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 ymin´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 lasconvenciones 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
Σ, Γ Σ∗ a, b, c, d, e,. . . u, v, w, x, y, z, . . . α, β, γ, . . . λ denotan alfabetos. denota el conjunto de todas las cadenas que se pueden formar con los s´ ımbolos del alfabeto Σ. denotan s´ ımbolos de un alfabeto. denotancadenas, 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´ con la letra griega ε. Preferimos ıa denotarla con λ porque ε tiende a confundirse con el s´ ımbolo ∈ usado para la relaci´n depertenencia. 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 cuatro objetos, que son todos diferentes entre s´ ∅, λ, {∅} y {λ}. ı:  La mayor parte de la teor´ de lenguajes se hace con referencia a un ıaalfabeto Σ fijo (pero arbitrario).

Cap´ ıtulo 1

Alfabetos, cadenas y lenguajes

3

1.2.

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 define descriptivamente as´ ı: 1. Si v = λ, entonces u · λ = λ · u = u. Es decir, la concatenaci´n de cualquier o cadena u con la cadena vac´ a izquierda oa 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. La concatenaci´n de cadenas se puede definir inductiva o recursivamente de la o siguiente manera. Si u, v ∈ Σ∗ , a ∈ Σ, entonces 1. u · λ = λ · u = u. 2. u ·...