lunes, 16 de febrero de 2015

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.

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.

Universo del discurso.

Es un conjunto de todas las cadenas donde podemos formar con símbolos del alfabeto V le denominamos universo del discurso de V y la representamos de la siguiente manera W (V). Es evidente que W(V) es un conjunto infinito y que la cadena vacía pertenece a W(V).

Ejemplo:


Un afabeto con una sola letra V = { a }, podemos decir que el universo del discurso es: W(V) = { λ, a, aa, aaa, aaaa,....} y asi contiene una cadenas infinitas.
_________________________________________________________________________________

Equipo: Anahi Jaramillo Hernandez, Erick Rios Garcia. Luis Antonio Martinez Sanchez.Alejandro Gomez Perez.

No hay comentarios:

Publicar un comentario