1.2.- 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

Concatenación de cadenas.

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

Ejemplo:

Sea u = ab

v = ca

w = bb. Entonces

uv = abca

uw = cabb

(uv) w = abcabb

u(vw) = abcabb

El resultado de la concatenación de u, v y w es independiente del orden en que las operaciones son ejecutadas. Matemáticamente esta propiedad es conocida como asociatividad.

Ø EJEMPLO: si ∑= {0,1}, entonces ∑1= {0,1}, ∑2= {00, 01, 10, 11}, ∑3= {000, 001, 010, 011, 100, 101, 110, 111}, etc.

Cadena Vacía.

La cadena vacía es aquella cadena que presenta cero apariciones de símbolos. Esta cadena, designada por £, es una cadena que puede construirse en cualquier alfabeto.

Ø EJEMPLO: observe que ∑0= {£}, independientemente de cuál sea el alfabeto ∑. Es decir, £ es la única cadena cuya longitud es 0.

http://www.academia.edu/15275019/Lenguajes_y_Aut%C3%B3matas_1