Teoria computacional

 Operaciones con cadenas
Concatenación
Si  y  son cadenas, la concatenación de éstas dos cadenas resulta en la cadena que se obtiene al agregar la segunda al final de la primera, es decir, sitenemos  y , la concatenación de estas dos cadenas es  y se denota  o , por lo que podemos observar que . La concatenación de cualquier cadena  con la cadena vacía  deja intacta a la cadena.

Igualdad(comparación)

La igualdad entre cadenas se denota con el signo `' y se da cuando dos o más cadenas tienen exactamente los mismos símbolos en la misma posición y tienen la misma longitud. Ejemplo: Si  y, entonces. 

Potencia 

La potencia de una cadena sobre un alfabeto quiere decir que tomamos toda la cadena como una unidad atómica, es decir, si , entonces  y así sucesivamente. Loanterior lo podemos simplificar con la siguiente definición.

Por lo tanto si  sobre el alfabeto, tenemos que

y podemos continuar hasta la i-ésima potencia de , que denotaremos como . 


Sufijo yprefijo
Ahora trataremos con el sufijo y el prefijo de una cadena, si tenemos una cadena, donde  y  también son cadenas, entonces  es el prefijo de  y  es el sufijo, hay que recordar que la cadenavacía puede ser el prefijo de cualquier cadena, además, si tenemos que, donde  es el prefijo de  y , entonces resulta que , lo cual indica que toda cadena es prefijo de si misma. 
Subcadena o subpalabraUna cadena  es una subcadena o subpalabra de otra cadena, si existen cadenas  y  para las cuales. 
Inversa o transpuesta
Para ver cómo funciona la definición anterior utilizaremos un ejemplo, si setiene , al aplicar la definición, se logra lo siguiente:

La inversa de una cadena tiene ciertas características, con la concatenación de cadenas, por ejemplo, si se tienen cadenas ab y cd que alconcatenarse forman abcd, sabemos que, de lo cual podemos observar que. Por lo tanto, si  y  son cadenas y si, entonces. 
La inversa se anula a sí misma, es decir, si a una cadena  se le aplica la...