sábado, 1 de octubre de 2016
Cadenas o Strings
Es una secuencia finita de símbolos.
Ejemplo:
a, b y c son
símbolos y abcb es una cadena.
Tipos de Cadenas:
Cadena Vacía:
Denotada
por e es la cadena que consiste en cero símbolos. Por ende tiene longitud |e
|=0.
Longitud:
Si w es
una cadena sobre cualquier alfabeto, su longitud se denota como |w |. La
longitud de w es el número de símbolos que tiene la cadena
Ejemplo:
abcb tiene longitud |w | =4.
Concatenación:
Es
la cadena que se forma al escribir la primera seguida de la segunda, sin que
haya espacio entre ellas. La concatenación de las cadenas w y z se
denota como wz ó w.z.
Ejemplo:
Si w=
"banana" y z= "rama", la concatenación de w con z es
la cadena "bananarama. Es decir, e w= we =w para cada cadena w.
Potencia de Cadenas:
La
noción de potencia de una cadena sobre un alfabeto es dada por la notación wk
que denota la concatenación de k copias de la cadena w.
Ejemplo:
Si w=122 sobre el alfabeto S ={1, 2}, se
tiene:
w0 = e
w1 = 122
w2 = 122122
w3 = 122122122
Sufijo:
Están
formados por los últimos símbolos de está. La cadena abc sus prefijos son: e, c, bc y
abc. Un sufijo de una cadena que no sea la misma cadena es un sufijo propio.
Sub Cadena:
Cadena
w es una subcadena o subpalabra de otra cadena z si existen las cadena x e y
para las cuales z= xwy.
La Transpuesta:
La
inversa o transpuesta de una cadena w es la imagen refleja de w. Para denotar
la inversa de w se usa wI
Por ejemplo:
si w = "able" entonces
su inversa es "elba".
