Teoria de la computación

Cap´ ıtulo 1 Lenguajes formales
1.1. Alfabetos y palabras

Un alfabeto es un conjunto finito no vac´ cuyos elementos se llaman s´ ıo ımbolos. Denotamos un alfabeto arbitrario con la letra Σ. Una palabra o cadena sobre un alfabeto Σ es cualquier sucesi´n finita de eleo mentos de Σ. Admitimos la existencia de una unica palabra que no tiene s´ ´ ımbolos, la cual se denomina palabra vac´ y se denotacon λ. La palabra vac´ desemıa ıa pe˜a, en la teor´ de lenguajes formales, un papel similar al que desempe˜a el n ıa n conjunto 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 palabras sobre Σ: aba ababaaa aaaab Obs´rvese que aba = aab. El orden de los s´ e ımbolos en una palabra es significativo ya quelas palabras se definen como sucesiones, es decir, conjuntos secuencialmente ordenados. El conjunto de todas las palabras sobre un alfabeto Σ, incluyendo la palabra 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, . . .}. Observaciones: 1. Si bien un alfabeto Σ es un conjunto finito, Σ∗es siempre un conjunto 1

2

Teor´ de la Computaci´n (15410) 2003-I. ıa o

Profesor: Rodrigo De Castro

infinito (enumerable). En el caso m´s simple, Σ contiene solo un s´ a ımbolo, ∗ Σ = {a}, y Σ = {λ, a, aa, aaa, aaaa, aaaaa, . . .}. 2. Hay que distinguir entre los siguientes objetos, que son todos diferentes entre s´ ı: ∅ λ {∅} {λ} 3. La teor´ de lenguajes se hace con referencia a unalfabeto Σ fijo (pero ıa arbitrario).

Notaci´n usada en la teor´ de lenguajes o ıa
Σ Σ∗ a, b, c, d, e,. . . u, v, w, x, y, z,. . . λ A,B,C,. . . ,L,M,N,. . . denota un alfabeto. denota el conjunto de todas las palabras que se pueden formar con los s´ ımbolos de Σ. denotan s´ ımbolos del alfabeto Σ. denotan palabras, es decir, sucesiones finitas de s´ ımbolos de Σ. denota la palabra vac´ es decir,la unica palabra ıa, ´ ∗ en Σ que no tiene s´ ımbolos. denotan lenguajes (definidos m´s adelante). a

1.2.

Concatenaci´n de palabras o

Dado un alfabeto Σ, y dos palabras 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 palabra u con la palabravac´ 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 b1 b2 · · · bm . Es decir, u · v es la palabra formada escribiendo los s´ ımbolos de u y a continuaci´n los s´ o ımbolos de v. La concatenaci´n de palabras se puede definir inductiva o recursivamente de la o siguiente manera. Si u, v ∈ Σ∗ , a ∈ Σ, entonces 1. u · λ = λ · u =u.

Cap´ ıtulo 1

Lenguajes formales

3

2. u · (va) = (u · v)a. Propiedad. La concatenaci´n de palabras es una operaci´n asociativa. Es decir, o o ∗ si u, v, w ∈ Σ , entonces (uv)w = u(vw). Demostraci´n: Se puede hacer escribiendo expl´ o ıcitamente las palabras u, v, w y usando la definici´n descriptiva de concatenaci´n. Tambi´n se puede dar una o o e demostraci´n inductiva usando ladefinici´n recursiva de concatenaci´n (ejercicio o o o opcional).

1.3.

Potencias de una palabra
u0 = λ, un = uu · · · u
n veces

Dada u ∈ Σ∗ y n ∈ N, se define (descriptivamente) un en la siguiente forma

§ ¦

Ejercicio

¤ ¥

Dar una definici´n recursiva de un . o

1.4.

Longitud de una palabra

La longitud de una palabra u ∈ Σ∗ se denota |u| y se define como el n´mero de u s´ımbolos de u (contando los s´ ımbolos repetidos). Es decir, |u| =
§ ¦ § ¦

0, si u = λ, n, si u = a1 a2 · · · an

Ejemplo Ejemplo

¤ ¥ ¤ ¥

|aba| = 3, |baaa| = 4. Si w ∈ Σ∗ , n, m ∈ N, demostrar que |wn+m | = |wn | + |wm |

Soluci´n: o Caso n, m ≥ 1. |wn+m | = | ww · · · w | = (n + m)|w|. Por otro lado,
n+m veces

|wn | + |wm | = | ww · · · w | + | ww · · · w | = n|w| + m|w|.
n...