lenguajes

´
Lenguajes formales y automatas
˜
Raul
R.
´ E Gutierrez de Pinerez
raul.gutierrez@correounivalle.edu.co

˜
Raul
´ E Gutierrez de Pinerez
R

Marzo, 2014

Lenguajes formales

˜
Raul
R
´ E Gutierrez de Pinerez

El alfabeto
Un alfabeto es un conjunto finito no vac´ıo cuyos elementos se llaman
s´ımbolos.
Sea Σ = {a, b} el alfabeto que consta de los s´ımbolos a y b. Las
siguientes son cadenas sobreΣ: aba, abaabaaa, aaaab.
El alfabeto binario Σ = {0, 1} son las cadenas sobre Σ que se
definen como secuencias finitas de ceros y unos.
Las cadenas son secuencias ordenadas y finitas de s´ımbolos.
Por ejemplo, w = aaab = w1 = baaa.
Sea Σ = {a, b, c, . . . , x, y, z} el alfabeto del idioma castellano.
´
El alfabeto utilizado por muchos lenguajes de programacion.
Sea Σ = {a, b, c} entonces podemosformar todas las cadenas
sobre Σ incluyendo la cadena vac´ıa.

Lenguajes formales

˜
Raul
R
´ E Gutierrez de Pinerez

´ de alfabetos, cadenas y lenguajes
Notacion

Si bien un alfabeto Σ es un conjunto finito, Σ∗ es siempre un
conjunto infinito (enumerable).
Hay que distinguir entre los siguientes cuatro objetos, que son
diferentes entre s´ı: ∅, , {∅}, { }
Lenguajes formales

˜
Raul
R
´ E Gutierrezde Pinerez

Conjunto Universal
El conjunto de todas las cadenas sobre un alfabeto Σ, incluyendo la
cadena vac´ıa, se denota por Σ∗
Sea Σ = {0, 1}
Σ∗ ??
Sea Σ = {a, b, c}, entonces
Σ∗ =??
Sea Σ = {a, b}, entonces
Σ∗ =??

Lenguajes formales

˜
Raul
R
´ E Gutierrez de Pinerez

Conjunto Universal
El conjunto de todas las cadenas sobre un alfabeto Σ, incluyendo la
cadena vac´ıa, se denota por Σ∗
Sea Σ= {0, 1}
Σ∗ = { , 0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 010, 110, . . .}
Sea Σ = {a, b, c}, entonces
Σ∗ = { , a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, abc, baa, . . .}
Sea Σ = {a, b}, entonces
Σ∗ = { , a, b, aa, ab, ba, bb, aaa, aab, baa, . . .}

Lenguajes formales

˜
Raul
R
´ E Gutierrez de Pinerez

´ de cadenas
Concatenacion

Cadenas
´ de u y
Dado un alfabeto Σ y dos cadenasu, v ∈ Σ∗ , la concatenacion
v se denota como u · v o simplemente uv y se define as´ı:
1
´ de
Si v = , entonces u · = · u = u, es decir, la concatenacion
cualquier cadena u con la cadena vac´ıa, a izquierda o derecha,
es igual a u.
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 cadena formada de escribir los s´ımbolos de u
´ loss´ımbolos de v.
y a continuacion

Lenguajes formales

˜
Raul
R
´ E Gutierrez de Pinerez

Potencia de una cadena

Dada w ∈ Σ∗ y n ∈ N , se define wn de la siguiente forma

si n = 0

wn =
ww . . . w si n ≥ 1

n−veces

Potencia de una cadena de manera recursiva
La potencia de una cadena se define como w ∈ Σ∗ para n ∈ N
wn =

,
si n = 0
wwn−1 , si n > 0

Ejemplo. Sea una cadena w = acc sobre Σ ={a, c} entonces
podemos obtener w3 = ww2 = wwww0 = accaccacc = (acc)3

Lenguajes formales

˜
Raul
R
´ E Gutierrez de Pinerez

Inversa de una cadena

Longitud de una cadena
La longitud de una cadena w ∈ Σ∗ se denota |w| y se define como el
numero
de s´ımbolos de w (contando los s´ımbolos repetidos), es
´
decir:
0, si w = ε
|w| =
n, si w = a1 a2 . . . an
|aba| = 3, |baaa| = 4
´ o inversa de unacadena
Reflexion
´ o inversa de una cadena w ∈ Σ∗ se denota como wI y se
La reflexion
define as´ı:
wI =

,
si w = ε
an . . . a2 a1 , si w = a1 a2 . . . an

Lenguajes formales

˜
Raul
R
´ E Gutierrez de Pinerez

Inversa de una cadena de manera recursiva
La Inversa de una cadena Sea u ∈ Σ∗ entonces u−1 es la inversa.
uI =

u
yI a

si u = ε
si u = ay, a ∈ Σ, y ∈ Σ∗

Lenguajes formales

˜
Raul
R
´ EGutierrez de Pinerez

Inversa de una cadena de manera recursiva
La Inversa de una cadena Sea u ∈ Σ∗ entonces u−1 es la inversa.
uI =

u
yI a

si u = ε
si u = ay, a ∈ Σ, y ∈ Σ∗

Sea x=’able’ entonces obtener xI
xI = (able)I = (ble)I a
= (le)I ba
= (e)I lba
= (ε)I elba
= εelba
= elba
´ de las cadenas “ab” y “cd” que forma
Sea la concatenacion
“abcd” sobre un alfabeto. Sabemos que (abcd)I = dcba,...