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