1.2 - Cadenas

Cadenas.

Una cadena o palabra sobre un alfabeto Σ. admitimos la existencia de una única cadena que no tiene símbolos, la cual se denomina cadena vacía y se denota con λ. la cadena vacía desempeña, en la teoría de lenguajes formales, un papel similar al que desempeña el conjunto vacío Ø en la teoría de conjuntos.

Longitud de cadena.

La longitud de cadena es el numero de símbolos que contiene. La notación empleada es la que es la que se indica en el ejemplo:

Utilizamos las cadenas de los ejemplos:

I abcb I = 4,

I a + 2*b I = 5

I 000111 I = 6

I if a > b then a = b; I = 9

Cadena Vacía.

Una cadena vacía es la única cadena de caracteres de tamaño cero. Y la podemos denotar usualmente con letras λ o Є (Griegas).

Concatenación de cadenas.

La concatenación de dos cadenas u y v, escrita uv, es "pegar" las dos cadenas para formar una nueva.