Una cadena sobre algún alfabeto es una secuencia finita de símbolos tomados de ese alfabeto. En teoría del lenguaje, los términos frase y palabra a menudo se utilizan como sinónimos del término "cadena". La longitud de una cadena s, que suele escribirse lsl, es el número de apariciones de símbolos en s. Por ejemplo, camino es una cadena de longitud seis. La cadena vacía, representada por Є, es una cadena especial de longitud cero.
