español

EISC

Aut´matas
o

Alfabetos, Cadenas y Lenguajes
Definici´n 1
o
Un Alfabeto es cualquier conjunto finito, no
vac´
ıo.
Ejemplo 1
Sea Σ = {0, 1, 2, 3, . . . , 9} donde 0 ∈ Σ
Definici´n 2
o
Una cadena sobre Σ es cualquier secuencia
de elementos de longitud finita sobre Σ.
Longitud de una cadena
Sea x ∈ Σ∗ se denota por | x | y se define
como el n´mero de s´
u
ımbolos de x.
| x |=0, si x =
n, si x = a1a2 . . . an
0

EISC

Aut´matas
o

Observaci´n 1
o
| xy |=| x | + | y |, x, y ∈ Σ∗
Ejemplo 2
Sea Σ = {a, b}, u = aba y v = ba
uv = ababa, | uv |= 5, por otra parte
| u | + | v |= 3 + 2
Ejemplo 3
| aba |= 3 y | baaa |= 4
Ejemplo 4
Σ = {a, b}, entonces | aababa |= 6 es la longitud de la cadena.
Observaci´n 2
o
Hay una ´nica cadena de longitud cero soubre Σ, llamada cadena vac´a denotada por ,
ı
| |= 0
1

EISC

Aut´matas
o

Observaci´n 3
o
Si Σ es diferente de vac´ entonces Σ∗ es el
ıo,
conjunto de todas las cadenas sobre Σ. Se le
llama lenguaje universal.
Ejemplo 5
Sea Σ = {1} entonces :
Σ∗ = { , 1, 11, 111, 1111, . . .}
Observaci´n 4
o
Un alfabeto es simplemente un conjunto finito no vac´ dados Σ1 y Σ2 alfabetos, se
ıo,tiene Σ1 ∪ Σ2 tambi´n lo es, adem´s Σ1 ∩ Σ2,
e
a
Σ1 − Σ2 y Σ2 − Σ1.
Observaci´n 5
o
Σ∗ es un conjunto infinito ya que los alfabetos
no son vac´
ıos, es decir si Σ no es vac´ enıo,
tonces Σ∗ es un conjunto infinto de cadenas
de longitud finita.
Concatenaci´n de cadenas
o
2

EISC

Aut´matas
o

La operaci´n de la concatenaci´n · es una
o
o
operaci´n binaria entre cadenas delalfabeto
o
Σ, esto es.
· : Σ∗ × Σ∗ → Σ∗
Sean x, y ∈ ∗ y se denota por x · y o simplemente xy
si x = a1a2 . . . an y y = b1b2 . . . bm entonces
x · y = a1a2 . . . anb1b2 . . . bm
Observaci´n 6
o
Sea (Σ∗, ·, ) es un monoide, con las siguientes
propiedades.
La concatenaci´n es cerrada. ∀x, y ∈ Σ∗,
o
x · y ∈ Σ∗

La concatenaci´n de cadenas es asociativa.
o
∀x, y, z ∈ Σ∗, (xy)z = x(yz)la cadena vac´
ıa
es la id´ntica para la
e
concatenaci´n: ∀x ∈ Σ∗, x = x = x
o
3

EISC

Aut´matas
o

Potencia de una cadena
se define como x ∈
xn =

∗ para n ∈ N

,
si n = 0
x · xn−1, si n ≥ 1

Ejemplo 6
Sobre Σ = {a, b},
(aab)0 = ,
(aab)1 = aab,
(aab)5 = aabaabaabaabaab
Observaci´n 7
o
(∀n)(n ∈ N, | xn |= n | x |)
Observaci´n 8
o
Si w ∈ Σ∗,
(∀m)(∀n)(m, n ∈ N →|wn+m |=| wn | + | wm |
)

Caso 1. n, m ≥ 1
| wn+m |=| ww · · · w |= (n + m) | w | por
n+m,veces
4

EISC

Aut´matas
o

otro lado,
| wn | + | wm |=| ww · · · w | + | ww · · · w |=
n,veces

m,veces

n | w | +m | w |

Caso 2. n = 0, m ≥ 1
| wn+m |=| w0+m |=| wm |, por otro lado,
| wn | + | wm |=| w0 | + | wm |=| | + |
wm |= 0+ | wm |=| wm |

Caso 3. m = 0, n ≥ 1 Similar alcaso anterior.

Caso 4. n = 0, m = 0
| wn+m |=| w0+0 |=| |= 0, por otro lado,
| wn | + | wm |=| w0 | + | w0 |=| | + |
|= 0 + 0 = 0

Sufijos y prefijos
Definici´n 3
o
5

EISC

Aut´matas
o

Decimos que una cadena z es subcadena de
otra cadena w si existen cadenas x, y ∈ Σ∗ tal
que w = x · z · y
pref ijo(w) = {x ∈ Σ∗ | ∃z ∈ Σ∗ : w = x · z}
suf ijo(w) = {x ∈ Σ∗ | ∃z ∈ Σ∗ : w = z ·x}

Un prefijo de una cadena x es una subcadena inicial de x, es decir una cadena
y es un prefijo si existe una cadena z tal
que x = yz y de manera similar z es un
sufijo de x.

Los prefijos propios son aquellas cadenas
que son prefijos de una palabra pero no
iguales a la misma.

Un prefijo y de x es un prefijo propio de
x si y = y y = x

Un sufijo z de x es un sufijo propio de x
si z =y z = x
6

EISC

Aut´matas
o

Ejemplo 7
Sea x = 121 es un prejijo de la cadena w =
121 pero no prefijo propio, adem´s x es un
a
sufijo de w = 121 pero no sufijo propio.
Inversa de una cadena
Sea x ∈
xI =

∗ entonces x−1 es la inversa.

x
si x = ε
y I a si x = ay, a ∈ Σ, y ∈ Σ∗

Sea x = able entonces obtener xI
xI = (able)I = (ble)I a
= (le)I ba
= (e)I lba
= (ε)I elba
=...