Conjunto no vacío y finito de elementos, distintos
entre sí e identificados, por ejemplo: números,
letras, combinaciones entre ellos.
Simbología:

Ejemplo: sea
=
y
“2 es un símbolo del alfabeto” se denota: 2
.
Otros ejemplos: =

= ,
el alfabeto de letras mayúsculas.
=
,
el alfabeto binario
Operaciones
con Alfabetos
Los Alfabetos, en su condición de conjuntos, pueden
ser sometidos a las operaciones clásicas de la
Teoría
de Conjuntos, es decir Unión,
Intersección, Diferencia y Complementación de
Conjuntos.
Las propiedades más importantes de dichas
operaciones son:
·
Si
=
·
Si
=
·
(
)
= (
)
·
(
)
= (
)
·
(
)
= (
)
(
)
·
(
)
= (
)
(
)
·
=
y
=

Potencia de un alfabeto
Si es
un alfabeto, es posible expresar el conjunto de
todas las cadenas de cierta longitud de dicho
alfabeto utilizando una notación exponencial.
Definimos como .
Como el conjunto de cadenas de longitud k, tales que
todos los símbolos que las forman pertenecen a .
Ejemplo:
Si = ,
entonces = ; = ;
=
Nótese además que independiente, de cual sea el
alfabeto siempre = ,
siendo la
única cadena cuya longitud es 0.
Otra cuestión que se presta a confusión es la
diferencia que existe entre = ,
y = ,
donde la primera es un alfabeto con símbolos cero y
uno y el segundo es un conjunto de cadenas de
longitud unitaria.
PALABRA
Se llama Palabra, Cadena o Tira a la concatenación o
secuencia finita de elementos de un alfabeto.
Simbología:
Las palabras se denotan con las últimas letras del
alfabeto en minúscula (x = “001” , y = “ai”)
Ejemplo:

Longitud de una
palabra.
Cada palabra tiene su longitud, es decir, el número
o la cantidad de elementos que la componen.
Simbología:
(se
utilizan dos barras a los costados de la palabra)
Ejemplo: sean las palabras: x = “001”, y =
“ai”, z = “ZXABK”
= 3
= 2
= 5
La
longitud de una palabra o cadena puede asumir
distintos valores, si la longitud es igual a 1, la
palabra es igual al elemento o símbolo del alfabeto,
es decir, que cada elemento o símbolo de un alfabeto
puede ser una tira o cadena del mismo.
Ejemplo: “0”
“A”

Palabra Vacía.
Si la longitud de una palabra es igual a 0, estamos
frente a una palabra que existe pero que no contiene
elementos, llamada “palabra vacía” y es una cadena
sobre cualquier alfabeto.
Simbología:
=
0
Subpalabras: Prefijo y Sufijo.
Se denota Sufijo a la subcadena
de una palabra dada formada por los primeros
símbolos de la misma y Prefijo a la subcadena
formada por los últimos símbolos de dicha palabra,
es decir, sea v una cadena sobre una
alfabeto, se llama Sufijo a la subcadena x
y Prefijo a la subcadena y de v,
tal que v = xy
Ejemplo: v = “aeiou”
= 3
x
= “aei”
=
2
x
= “ou”
Universo de discurso
Se llama Universo de Discurso o Lenguaje
Universal al conjunto de todas las cadenas,
tiras o palabras que se pueden formar con los
elementos o símbolos de un alfabeto, incluida la
palabra vacía.
Simbología:
El
es
una conjunto infinito ya que son infinitas las
palabras o cadenas que puedo formar con los símbolos
de un alfabeto ya que éstos no son vacíos.
Ejemplo:

Operaciones palabras
Concatenación
La
Concatenación de dos palabras (s, t) da origen a una
nueva palabra (r) formada por los elementos o
símbolos de la primera palabra seguidos los símbolos
de la segunda, es decir, r = s
t
Ejemplo: siendo las palabras:
s = “abc” t = “defg”
r = s
t
= “abcdefg”
Simbología:
la concatenación se indica con un punto entre las
palabras a concatenar.
La concatenación se puede realizar entre
la palabra vacía y cualquier palabra, teniendo como
resultado la misma palabra sin ser modificada.
Ejemplo:
s
=
s
= s
Propiedades de la operación Concatenación:
§
Propiedad Conmutativa: ésta propiedad no se cumple
para esta operación: s
t
¹ t
s
§
Operación Cerrada: la concatenación de dos palabras
que pertenecen a
es
también una palabra de
.
§
Propiedad Asociativa: (r
s)
t
= r
(s
t)
Potenciación
Se llama Potencia de una palabra v a la nueva
palabra z que se obtiene de haber concatenado
v consigo misma tantas veces como indica el
exponente:
= v. v. v. v. v. v. ... n
Ejemplo:
sea v = “011”
Z =
=
v = “011”
Z =
=
v
v
= “011011”
Z =
=
v
v
v
= “011011011”
Toda potencia 0 de una palabra, por definición, es
la palabra vacía:

Reflexión
La Reflexión o refleja de una palabra o cadena x,
se forma invirtiendo el orden de los símbolos o
elementos de la misma.
Ejemplo:
x = “abc”
=
“cba”
|