Cadena vacía

En la teoría del lenguaje formal , la cadena vacía , también conocida como palabra vacía o cadena nula , es la única cadena de longitud cero.

Formalmente, una cadena es una secuencia finita y ordenada de caracteres como letras, dígitos o espacios. La cadena vacía es el caso especial en el que la secuencia tiene longitud cero, por lo que no contiene símbolos. Solo existe una cadena vacía, ya que dos cadenas solo se diferencian si tienen longitudes distintas o secuencias de símbolos diferentes. En los tratamientos formales, ^{[ 1 ]} la cadena vacía se denota con ε o, a veces, con Λ o λ .

La cadena vacía no debe confundirse con el lenguaje vacío ∅ , que es un lenguaje formal (es decir, un conjunto de cadenas) que no contiene ninguna cadena, ni siquiera la cadena vacía.

La cadena vacía tiene varias propiedades:

• |ε| = 0. Su longitud de cadena es cero.
• ε ⋅ s = s ⋅ ε = s. La cadena vacía es el elemento neutro de la operación de concatenación . El conjunto de todas las cadenas forma un monoide libre con respecto a ⋅ y ε.
• ε ^R = ε. La inversión de la cadena vacía produce la cadena vacía, por lo que la cadena vacía es un palíndromo .
• ${\displaystyle \forall c\in s:P(c)}$Las afirmaciones que se refieren a todos los caracteres de una cadena son trivialmente verdaderas .
• La cadena vacía precede a cualquier otra cadena en el orden lexicográfico , porque es la más corta de todas las cadenas. ^{[ 2 ]}

En las gramáticas libres de contexto , una regla de producción que permite que un símbolo produzca la cadena vacía se conoce como una ε-producción, y se dice que el símbolo es "anulable".

En la mayoría de los lenguajes de programación , el término "cadena" suele referirse a instancias de un tipo de dato , por lo que constituye un concepto distinto al de la teoría formal. Estas cadenas se almacenan normalmente en direcciones de memoria distintas y, por lo tanto, poseen identidad. Así, las representaciones de una misma cadena formal (por ejemplo, la cadena vacía) pueden almacenarse en dos o más ubicaciones de memoria y pueden considerarse nombres de la cadena vacía formal.

De esta forma, podría haber múltiples representaciones de la cadena vacía en memoria, a diferencia de la definición teórica formal, que solo contempla una posible cadena vacía. Sin embargo, una función de comparación de cadenas indicaría que todas estas representaciones son iguales entre sí.

Incluso una cadena de longitud cero puede requerir memoria para su almacenamiento, dependiendo del formato utilizado. En la mayoría de los lenguajes de programación, la cadena vacía se distingue de una referencia nula (o puntero nulo) porque una referencia nula no apunta a ninguna cadena, ni siquiera a la cadena vacía. La cadena vacía es una cadena válida, sobre la cual deberían funcionar la mayoría de las operaciones de cadena. Algunos lenguajes tratan algunos o todos los siguientes elementos de forma similar: cadenas vacías, referencias nulas, el entero 0, el número de coma flotante 0, el valor booleano falso , el carácter ASCII NUL u otros valores similares.

La cadena vacía se representa normalmente de forma similar a otras cadenas. En implementaciones con caracteres de terminación de cadena ( cadenas terminadas en nulo o líneas de texto plano), la cadena vacía se indica mediante el uso inmediato de este carácter.

En distintos lenguajes de programación, existen diferentes funciones, métodos, macros o expresiones idiomáticas para comprobar si una cadena está vacía.

• Conjunto vacío
• Cadena terminada en nulo
• Teoría de la concatenación
• Literal de cadena