Longitud de una cadena y potencia de alfabeto

 Longitud de una cadena

Suele ser útil clasificar las cadenas por su longitud, es decir, el número de posiciones ocupadas por símbolos dentro de la cadena. Por ejemplo, 01101 tiene una longitud de 5. Es habitual decir que la longitud de una cadena es igual al “número de símbolos” que contiene; esta proposición está aceptada coloquialmente, sin embargo, no es estrictamente correcta. Así, en la cadena 01101 sólo hay dos símbolos, 0 y 1, aunque tiene cinco posiciones para los mismos y su longitus es igual a 5. Sin embargo, generalmente podremos utilizar la expresión “número de símbolos” cuando realmente a lo que se está haciendo referencia es al “número de posiciones”. La notación estándar para indicar la longitud de una cadena w es |w|. Por ejemplo, |011| = 3 y |ε| = 0.

Potencias de un alfabeto

Si Σ es un alfabeto, podemos expresar el conjunto de todas las cadenas de una determinada longitud de dicho alfabeto utilizando una notación exponencial. Definimos Σk para que sea el conjunto de las cadenas de longitud k, tales que cada uno de los símbolos de las mismas pertenece a Σ.

EJEMPLO 1.24

Observe que Σ0 = {ε}, independientementede cuál sea el alfabeto Σ. Es decir, ε es la única cadena cuya longitud

es 0.

Si Σ = {0,1}, entonces Σ1 = {0,1}, Σ2 = {00,01,10,11}, Σ3 = {000,001,010,011,100,101,110,111},

etc.

Observe que existe una ligera confusión entre Σ y Σ1. Lo primero es un alfabeto; sus elementos 0 y 1 son los símbolos. Lo segundo es un conjunto de cadenas; sus elementos son las cadenas 0 y 1, cuya longitud es igual a 1. No vamos a utilizar notaciones diferentes para los dos conjuntos, confiando en que el contexto deje claro si {0,1} o algún otro conjunto similar representa un alfabeto o un conjunto de cadenas. ✷ Por convenio, el conjunto de todas las cadenas de un alfabeto Σ se designa mediante Σ∗. Por ejemplo,

{0,1}∗ = {ε,0,1,00,01,10,11,000,...}. Expresado de otra forma,

Σ∗ = Σ0 ∪ Σ1 ∪ Σ2 ∪···

En ocasiones, desearemos excluir la cadena vacía del conjunto de cadenas. El conjunto de cadenas no vacíasm del alfabeto Σ se designa como Σ+. Por tanto, dos equivalencias apropiadas son:

Σ+ = Σ1 ∪ Σ2 ∪ Σ3 ∪···.

Σ∗ = Σ+ ∪ {ε}.