Siguiente: Orden lexicográfico Un nivel arriba: Relaciones de orden Anterior: Relaciones de orden

Orden de prefijo

Primeramente presentamos condiciones necesarias y suficientes para comparar cadenas y subcadenas.

Teorema 2.1 (Levi)   Sean $\sigma_1,\sigma_2,\tau_1,\tau_2\in\Sigma^*$ tales que $\sigma_1\tau_1=\sigma_2\tau_2$. Entonces se cumplen las implicaciones siguientes:

1.

$\mbox{\it long\/}(\sigma_1)\geq\mbox{\it long\/}(\sigma_2)\Rightarrow\exists!\u... ...n\in\Sigma^*\left( \sigma_1=\sigma_2\upsilon\;\&\;\upsilon\tau_1=\tau_2\right)$

2.

$\mbox{\it long\/}(\sigma_1)=\mbox{\it long\/}(\sigma_2)\Rightarrow\left( \sigma_1=\sigma_2\;\&\;\tau_1=\tau_2\right)$

3.

$\mbox{\it long\/}(\sigma_1)\leq\mbox{\it long\/}(\sigma_2)\Rightarrow\exists!\u... ...n\in\Sigma^*\left( \sigma_2=\sigma_1\upsilon\;\&\;\upsilon\tau_2=\tau_1\right)$

Gráficamente resulta muy clara la validez del teorema y por eso omitimos su demostración formal. Como una consecuencia directa de este teorema resulta el siguiente

Corolario 2.1   Si $\sigma_1,\sigma_2,\tau_1,\tau_2\in\Sigma^*$ son tales que $\sigma_1\tau_1=\sigma_2\tau_2$ entonces $\sigma_1$ es un prefijo de $\sigma_2$ o, recíprocamente, $\sigma_2$ es un prefijo de $\sigma_1$.

Recordamos que una relación de orden ``$\leq$'' en un conjunto S es una relación binaria $\left(\leq\right)\subset S^2$ tal que es reflexiva, transitiva y antisimétrica. Esto último significa que

$$\forall s,t\in S:\ (s\leq t)\&(t\leq s)\;\Rightarrow\;(s=t).$$

Del último corolario se ve fácilmente que la relación de prefijo:

$$\forall \sigma_1,\sigma_2\in\Sigma^*:\ (\sigma_1\leq_p\sigma_2)\Leftrightarrow (\sigma_1\mbox{\rm es un prefijo de }\sigma_2),$$

es, efectivamente, un orden en $\Sigma^*$. Hemos visto que $\Sigma^*$ no es conmutativo. Veremos a continuación algunas proposiciones relativas al orden de prefijo y a la contención, en general, entre cadenas.

Proposición 2.5   Si $\sigma_1,\sigma_2,\tau_1,\tau_2\in\Sigma^*$ son tales que $\sigma_1\leq_p\tau_1$ y $\sigma_2\leq_p\tau_1\tau_2$ entonces $\sigma_1\leq_p\sigma_2$ o $\sigma_2\leq_p\sigma_1$.

En efecto, las siguientes implicaciones son todas verdaderas:

$$\begin{eqnarray*}\left.\begin{array}{l} \sigma_1\leq_p\tau_1 \\ \sigma_2\leq_p\... ...Rightarrow}& (\sigma_1\leq_p\tau_1)\lor(\sigma_2\leq_p\sigma_1) \end{eqnarray*}$$

En el siguiente teorema veremos una condición necesaria para que una palabra sea a la vez prefijo y sufijo de alguna otra. Es evidente que la condición que ahí se establece es también suficiente.

Teorema 2.2   Sean $\sigma_1,\sigma_2\in\Sigma^*$ tales que $\sigma_1$ es prefijo y sufijo de $\sigma_2$, es decir

$$\exists\tau_1,\tau_2\in\Sigma^+:(\tau_2\sigma_1=\sigma_2)\&(\sigma_2=\sigma_1\tau_1).$$

Entonces,

$$\exists \upsilon_1,\upsilon_2\in\Sigma^*, k\geq 0:\ \left\{\b... ...on_1\left(\upsilon_2\upsilon_1\right)^{k+1} \end{array}\right.$$

En efecto, consideremos dos casos, según se comparen entre sí las longitudes de las palabras $\sigma_1$ y $\tau_2$.

$\mbox{\rm long}(\sigma_1)\leq\mbox{\rm long}(\tau_2)$:

Ya que $\tau_2\sigma_1=\sigma_1\tau_1$, por el teorema de Levy se tiene que $\sigma_1$ es un prefijo de $\tau_2$. Se ve pues que $\exists \upsilon_1\in\Sigma^+$ tal que $\tau_2=\sigma_1\upsilon_1$ y $\tau_1=\upsilon_1\sigma_1$. El teorema se cumple tomando $\upsilon_2=\sigma_1$ y k=0.

$\mbox{\rm long}(\sigma_1)>\mbox{\rm long}(\tau_2)$:

Probemos el teorema por inducción en $\mbox{\rm long}(\sigma_1)$. Para $\mbox{\rm long}(\sigma_1)=\mbox{\rm long}(\tau_2)$ el teorema se cumple pues se está en el caso anterior. Supongamos ahora que $\mbox{\rm long}(\sigma_1)>\mbox{\rm long}(\tau_2)$ y que el teorema se cumple para toda palabra $\sigma_{11}$ tal que $\mbox{\rm long}(\sigma_1)>\mbox{\rm long}(\sigma_{11})\geq\mbox{\rm long}(\tau_2)$. Ya que $\tau_2\sigma_1=\sigma_1\tau_1$, por el teorema de Levy se tiene que, para alguna $\sigma_{11}\in\Sigma^*$

$$\sigma_1=\tau_2\sigma_{11} \ \ \ \&\ \ \ \sigma_1=\sigma_{11}\tau_1.$$

Por la hipótesis de inducción $\exists \upsilon_1,\upsilon_2\in\Sigma^*, k\geq 0:$

$$\left\{\begin{array}{rcl} \tau_1 &=& \upsilon_1\upsilon_2\\ ... ...on_1\left(\upsilon_2\upsilon_1\right)^{k+1} \end{array}\right.$$

y con esto queda demostrado el teorema.

Con el siguiente teorema vemos cuándo dos palabras dadas son ambas múltiplos de una misma partícula.

Teorema 2.3   Sean $\sigma_1,\sigma_2\in\Sigma^*$. Las siguientes aseveraciones son equivalentes:

1.

Ambas $\sigma_1,\sigma_2$ son múltiplos de una misma partícula, es decir,

$$\exists\tau\in\Sigma^*,\,n_1,n_2\in I\!\!N:\ \left(\sigma_1=\tau^{n_1}\right)\&\left(\sigma_2=\tau^{n_2}\right).$$

2.

Las palabras $\sigma_1$ y $\sigma_2$ poseen sendos múltiplos con un prefijo común de longitud

$$\mbox{\rm long}(\sigma_1)+\mbox{\rm long}(\sigma_2)-\mbox{\rm... ...eft(\mbox{\rm long}(\sigma_1),\mbox{\rm long}(\sigma_2)\right).$$

En símbolos,

$$\begin{eqnarray*}\exists\upsilon\in\Sigma^*,\,m_1,m_2\in I\!\!N&:& \left(\upsilo... ...left(\mbox{\rm long}(\sigma_1),\mbox{\rm long}(\sigma_2)\right) \end{eqnarray*}$$

Escribamos $k_i=\mbox{\rm long}(\sigma_i)$, i=1,2.

$1\Rightarrow 2$:

Supongamos que $\sigma_i=\tau^{n_i}$, i=1,2. Para i=1,2, hagamos

$$m_i=\left\lceil\frac{n_1+n_2-\mbox{\rm mcd}(n_1,n_2)}{n_i}\right\rceil,$$

donde $\lceil x\rceil$ denota al entero más chico por encima de x. Tenemos pues que, para i=1,2, $\sigma_i^{m_i}=\tau^{m_in_i}$. Puesto que $m_in_i\geq n_1+n_2-\mbox{\rm mcd}(n_1,n_2)$, se tiene que $\sigma_i^{m_i}$ contiene a la palabra $\upsilon=\tau^{n_1+n_2-\mbox{\scriptsize mcd}(n_1,n_2)}$, la cual tiene longitud

$$\mbox{\rm long}(\upsilon) = \mbox{\rm long}(\tau)\left(n_1+n_2-\mbox{\rm mcd}(n_1,n_2)\right) = k_1+k_2-\mbox{\rm mcd}(k_1,k_2)$$

$2\Rightarrow 1$:

Supongamos que $\upsilon$ es un prefijo común de $\sigma_i^{m_i}$, i=1,2, de longitud $k_1+k_2-\mbox{\rm mcd}(k_1,k_2)$. Supongamos, sin pérdida de generalidad, que $k_1\leq k_2$, e, inicialmente, que $\mbox{\rm mcd}(k_1,k_2)=1$. Escribamos $\sigma_i=s_{i0}\cdots s_{i,k_i-1}$. Como ambos $\sigma_1^{m_1}$ y $\sigma_2^{m_2}$ poseen un prefijo común de longitud k₁+k₂-1, se tiene que

$$\forall k<k_1+k_2-1:s_{1,k\mbox{\scriptsize mod }k_1}=s_{2,k\mbox{\scriptsize mod }k_2}.$$

En particular, $s_{1,(\kappa_2+k_2)\mbox{\scriptsize mod }k_1}=s_{2,\kappa_2}$, $\forall \kappa_2<k_2$. Y por tanto, $s_{1,(\kappa_1k_2)\mbox{\scriptsize mod }k_1}=s_{2,0}$, $\forall \kappa_1<k_1$. Ahora bien, como $\mbox{\rm mcd}(k_1,k_2)=1$, tenemos que el conjunto de índices $\{\left(\kappa_1k_2\right)\mbox{\rm mod }k_1\vert\kappa_1<k_1\}$ coincide con todo el intervalo [0,k₁-1]. Por tanto, tenemos que $\forall \kappa_1<k_1:s_{1,\kappa_1}=s_{2,0}$. Así pues, resulta válida la condición 1., con $\tau=s_{2,0}$, la cual es una palabra de longitud 1. En el caso de que $\mbox{\rm mcd}(k_1,k_2)=d>1$, consideremos el alfabeto $\Sigma'=\Sigma^d$. Entonces $\sigma_1$ y $\sigma_2$, vistas como palabras en $\left(\Sigma^d\right)^*$, tienen longitud $k_1'=\frac{k_1}{d}$ y $k_2'=\frac{k_2}{d}$ respectivamente, y aquí, $\mbox{\rm mcd}(k_1',k_2')=1$. Así, este caso se reduce al anterior y consecuentemente también en este caso resulta válida la condición 1.

Para concluir esta sección veamos una condición necesaria para que dos palabras conmuten bajo la operación de concatenación.

Proposición 2.6   Sean $\sigma_1,\sigma_2\in\Sigma^*$ dos palabras tales que $\sigma_1\sigma_2=\sigma_2\sigma_1$. Entonces

$$\exists\tau\in\Sigma^*,\,n_1,n_2\in I\!\!N:\ \left(\sigma_1=\tau^{n_1}\right)\&\left(\sigma_2=\tau^{n_2}\right).$$

En efecto, supongamos que $\sigma_1\sigma_2=\sigma_2\sigma_1$ y que $\mbox{\rm long}(\sigma_1)\geq\mbox{\rm long}(\sigma_2)$. Por el Teorema de Levy, existe una palabra $\sigma_{11}\in\Sigma^*$ tal que $\left(\sigma_1=\sigma_2\sigma_{11}\right)\& \left(\sigma_1=\sigma_{11}\sigma_2\right).$ Consecuentemente, $\sigma_{11}$ y $\sigma_2$ conmutan. Así, que por la misma razón, $\exists \sigma_{12}\in \Sigma^*:\left(\sigma_{11}=\sigma_2\sigma_{12}\right)\& \left(\sigma_{11}=\sigma_{12}\sigma_2\right).$ Consecutivamente, en tanto que $\mbox{\rm long}(\sigma_{1,\kappa-1})\geq\mbox{\rm long}(\sigma_2)$, se tendrá que ha de existir una $\sigma_{1,\kappa}\in \Sigma^*$ tal que $\left(\sigma_{1,\kappa-1}=\sigma_2\sigma_{1,\kappa}\right)\& \left(\sigma_{1,\kappa-1}=\sigma_{1,\kappa}\sigma_2\right).$ Así pues, $\exists q_1\in I\!\!N: \ \left(\sigma_{1}=\sigma_2^{q_1}\tau_1\right)\& \left(\... ...igma_2\right)\& \left(\mbox{\rm long}(\tau_1)<\mbox{\rm long}(\sigma_2)\right),$ donde $\tau_1=\sigma_{1,q_1}$. Igualmente, $\exists q_2\in I\!\!N:\ \left(\sigma_{2}=\tau_1^{q_2}\tau_2\right)\& \left(\tau... ..._2\tau_1\right)\& \left(\mbox{\rm long}(\tau_1)<\mbox{\rm long}(\tau_1)\right),$ donde $\tau_2=\sigma_{2,q_2}$. Reiterando este procedimiento construimos una sucesión de palabras $\left(\tau_k\right)_k$ tal que para todo k,

$$\left(\tau_{k-1}=\tau_k^{q_{k+1}}\tau_{k+1}\right)\& \left(\t... ...& \left(\mbox{\rm long}(\tau_k)<\mbox{\rm long}(\tau_k)\right).$$

Observe el lector la similitud que existe entre este procedimiento y el cálculo del máximo común divisor de $\mbox{\rm long}(\sigma_1),\mbox{\rm long}(\sigma_2)$ mediante el Algoritmo de Euclides. Como las longitudes de las palabras $\tau_i$ están decreciendo, en un momento se harán cero. Sea $\tau$ la última palabra no nula en esa sucesión. Pues bien, se tiene que $\exists n_1,n_2\in I\!\!N:\ \left(\sigma_1=\tau^{n_1}\right)\&\left(\sigma_2=\tau^{n_2}\right)$.
Siguiente: Orden lexicográfico Un nivel arriba: Relaciones de orden Anterior: Relaciones de orden