PALABRAS O CADENA

Una cadena o palabra es una secuencia finita de símbolos que pertenecen a un alfabeto y comunmente se denota con la letra . La cadena vacía se denota como  y es una secuencia vacía de símbolos tomados de cualquier alfabeto .

Sí el alfabeto es el español, algunas cadenas pueden ser ,  y . Dada la definición anterior, cualquier palabra que contenga los símbolos del alfabeto es una cadena válida, sin importar si esta tiene o no significado alguno.
Si  es cualquier cadena, su longitud se denota como , la longitud de una cadena es el número de símbolos que contiene, por ejemplo, si tenemos la cadena  sobre el alfabeto español, . La cadena vacía  no tiene símbolos, por lo que