Operaciones con cadenas

Ahora describiremos algunas de las características de las cadenas y operaciones básicas que se pueden realizar con ellas.
Si $w_1$ y $w_2$ 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, si tenemos $w_1=mesa$ y $w_2=banco$, la concatenación de estas dos cadenas es $mesabanco$ y se denota $w_1\cdot w_2$ o $w_1w_2$, por lo que podemos observar que $\vert w_1+w_2\vert=\vert w_1\vert+\vert w_2\vert$. La concatenación de cualquier cadena $w_1$ con la cadena vacía $\varepsilon$ deja intacta a la cadena $w_1$. La igualdad entre cadenas se denota con el signo `$=$' y se dá cuando dos o más cadenas tienen exactamente los mismos símbolos en la misma posición y tienen la misma longitud.
Ejemplo: Si $w_1=luz$ y $w_2=luz$, entonces $w_1=w_2$.
La potencia de una cadena sobre un alfabeto quiere decir que tomamos toda la cadena como una unidad atómica, es decir, si $w=abc$, entonces $w^2=ww, w^3=www$ y así sucecivamente. Lo anterior lo podemos simplificar con la siguiente definición.

$$\begin{array}{ll} w^n= & \left\{ \begin{array}{ll} \varepsil... ...=0\\ ww^{n-1} & \textrm{si}\ n>0 \end{array}\right.\end{array}$$

Por lo tanto si $w=ab$ sobre el alfabeto $\Sigma=\{a,b\}$, tenemos que

$$\begin{array}{l} w^0=\varepsilon\\ w^1=ab\\ w^2=abab\\ w^3=ababab, \end{array}$$

y podemos continuar hasta la i-ésima potencia de $w$, que denotaremos como $w^i$.
Ahora trataremos con el sufijo y el prefijo de una cadena, si tenemos una cadena $w=xy$, donde $x$ y $y$ también son cadenas, entonces $x$ es el prefijo de $w$ y $y$ es el sufijo, hay que recordar que la cadena vacía puede ser el prefijo de cualquier cadena, además, si tenemos que $c=xy$, donde $x$ es el prefijo de $c$ y $y=\varepsilon$, entonces resulta que $x=c$, lo cual indica que toda cadena es prefijo de si misma.
Una cadena $c$ es una subcadena o subpalabra de otra cadena $w$, si exiten cadenas $x$ y $y$ para las cuales $w=xcy$.
La inversa o transpuesta de una cadena $w$ se denota como $w^I$ y quiere decir que, si se tiene $w=taza$, entonces $w^I=azat$. Más generalmente podemos decir que

$$\begin{array}{ll} w^I= & \left\{ \begin{array}{ll} w, & \tex... ...igma \textrm{ y } y \in \Sigma^* \end{array}\right. \end{array}$$

Para ver como funciona la definición anterior utilizaremos un ejemplo, si se tiene $w=tabla$, al aplicar la definición, se logra lo siguiente:

$$\begin{array}{ll} w^I=(tabla)^I&=(abla)^It\\ &=(bla)^Iat\\ &=(l... ...)^Ilbat\\ &=(\varepsilon)^Ialbat\\ &=\varepsilon albat\\ &=albat \end{array}$$

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 al concatenarse forman abcd, sabemos que $(abcd)^I=dcba$, de lo cual podemos observar que $dcba=(cd)^I(ab)^I$. Por lo tanto, si $g$ y $h$ son cadenas y si $x=gh$, entoces $x^I=h^Ig^I$.
La inversa se anula a si misma, es decir, si a una cadena $w$ se le aplica la inversa dos veces seguidas, el resultado será $w$, como si no se hubiera aplicado ni una vez. Más generalmente, $(w^I)^I=w$.
Ejemplo:

$$\begin{array}{ll} ((abcd)^I)^I &=(dcba)^I\\ &=abcd \end{array}$$