next up previous contents
Next: Operaciones con lenguajes Up: Alfabetos y lenguajes Previous: Alfabetos, cadenas y lenguajes   Contents

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{displaymath}
\begin{array}{ll}
w^n= & \left\{
\begin{array}{ll}
\varepsil...
...=0\\
ww^{n-1} & \textrm{si}\ n>0
\end{array}\right.\end{array}\end{displaymath}

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

$\displaystyle \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{displaymath}
\begin{array}{ll}
w^I= & \left\{
\begin{array}{ll}
w, & \tex...
...igma
\textrm{ y } y \in \Sigma^*
\end{array}\right.
\end{array}\end{displaymath}

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:

$\displaystyle \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:

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


next up previous contents
Next: Operaciones con lenguajes Up: Alfabetos y lenguajes Previous: Alfabetos, cadenas y lenguajes   Contents
Pablo Gerardo Padilla Beltrán 2005-10-21