Siguiente: Presentación formal Un nivel arriba: Expresiones regulares Anterior: Expresiones regulares

Presentación conjuntista

Sea $\Sigma$ un alfabeto. Para dos lenguajes cualesquiera $K,L\subset \Sigma^*$ definimos

$$\begin{array}{l@{\ :\ }lcl} \mbox{\it yuxtaposici\'on o prod... .../} & K^*&=&{\displaystyle \bigcup_{n\geq 0}K^{n} } \end{array}$$

Denotemos por ${\cal P}(\Sigma^*)$ al conjunto de ``partes'' de $\Sigma^*$, es decir, a la colección de todos los lenguajes sobre el alfabeto $\Sigma$. A algunos lenguajes particulares se los distingue desde la manera en la que se los denota. Algunos de éstos son los siguientes:

$$\begin{array}{lcl} \mbox{\rm lenguaje vac\'\i o} &:& \mbox{\... ...gma\} \\ \mbox{\rm lenguaje total} &:& \Sigma^* \end{array}$$

Proposición 1.1   La estructura algebraica $({\cal P}(\Sigma^*),+,\cdot,\mbox{\bf0},\mbox{\bf 1})$ posee las propiedades siguientes:

$$\begin{array}{l@{\ :\ }rcl@{\ ;\ }rcl} \mbox{\it conmutativi... ...+ L\cdot M & K\cdot(L+M) &=& K\cdot L+ K\cdot M \end{array}$$ (12)

Además se cumplen también las propiedades siguientes: Producto

$$\begin{array}{l@{\ :\ }rcl@{\ ;\ }rcl} \mbox{\it nulidad\/} ... ...box{\bf0} & \mbox{\bf0}\cdot K&=& \mbox{\bf0}\\ \end{array}$$ (13)

Suma

$$\begin{array}{l@{\ :\ }rcl@{\ ;\ }rcl} \mbox{\it idempotencia\/} & K+K&=& K & % \end{array}$$ (14)

La verificación de las relaciones anteriores es rutinaria. Tenemos pues que $({\cal P}(\Sigma^*),+,\cdot,\mbox{\bf0},\mbox{\bf 1})$ tiene una estructura de semianillo, idempotente respecto a la adición.

Proposición 1.2 (Operación estrella)   En ${\cal P}(\Sigma^*)$ se cumplen las relaciones siguientes:

           

$$K\cdot K^* + \mbox{\bf 1}$$ K^* = (15)

$$\forall n\geq 1:\ \ K^* K^n\cdot K^* + \left(\sum_{i=0}^{n-1}K^i\right)$$ = (16)

$$\mbox{\bf0}^* \mbox{\bf 1}$$ = (17)

(KL)^*K = K(LK)^* (18)

(K+L)^* = (K^*L)^*K^* (19)

$$\mbox{\bf 1}+K(LK)^*L$$ (KL)^* = (20)

$$(\mbox{\bf 1}+K)^*$$ = K^* (21)

$$\mbox{\bf 1}+K^*$$ = K^* (22)

(K^*)^* = K^* (23)

$$\mbox{\bf 1}^* \mbox{\bf 1}$$ = (24)

K^*K^* = K^* (25)

En efecto, la ecuación (4.4) se sigue de las ecuaciones siguientes:

$$\sum_{n\geq 0} K^n = \sum_{n> 0} K^n + K^0 = K\sum_{n\geq 0} K^n + K^0.$$

La ecuación (4.5) se sigue al reiterar la ecuación (4.4). La ecuación (4.6) se sigue de la ecuación (4.4) y de la condición de nulidad (4.2). La ecuación (4.7) se sigue al desarrollar como sumas cada uno de sus miembros para ver que ambas constan de sumandos de la forma K(LK)ⁱ=(KL)ⁱK con $i\geq 0$. La ecuación (4.8) se sigue al desarrollar como sumas cada uno de sus miembros para ver que todo sumando en una suma aparece en la otra. La ecuación (4.9) se sigue de las ecuaciones (4.4) y (4.7). La ecuación (4.10) se sigue de la ecuación (4.4) y de que $\mbox{\bf 1}$ es una unidad multiplicativa, (ec's. 4.1). La ecuación (4.11) se sigue de la ecuación (4.4) y de la idempotencia, (ec. 4.3). La ecuación (4.12) se sigue de las siguientes ecuaciones, justificadas ya anteriormente:

$$\begin{array}{lclclcl} (K^*)^* &\stackrel{(1)}{=}& K^*\cdot ... ...=}& KK^* + \mbox{\bf 1} % &\stackrel{(6)}{=}& K^* \end{array}$$

pues la igualdad (1) es una forma de la ec. (4.4), la igualdad (2) lo es de la ec. (4.8), la igualdad (3) lo es de la ec. (4.10), la igualdad (4) lo es de la ec. (4.4), la igualdad (5) lo es de la ec. (4.3) y la igualdad (6) lo es de la ec. (4.4). La ecuación (4.13) se sigue de la ecuación (4.12) y de la ecuación (4.6) al tomar $K=\mbox{\bf0}$. La ecuación (4.14) se sigue de las siguientes ecuaciones, justificadas ya anteriormente:

$$\begin{array}{lclcl} K^* &\stackrel{(1)}{=}& (K + \mbox{\bf ... ...(3)}{=}& (K^*)^*K^* &\stackrel{(4)}{=}& K^*K^* \end{array}$$

pues la igualdad (1) es una forma de la ec. (4.10), la igualdad (2) lo es de la ec. (4.8), la igualdad (3) lo es de que $\mbox{\bf 1}$ es unidad multiplicativa y la igualdad (4) lo es de la ec. (4.12).


Diremos que un lenguaje $K\in{\cal P}(\Sigma^*)$ posee la condición de la palabra vacía (CPV) si $\mbox{\it nil\/}\in K$.

Lema 1.1   Sea K un lenguaje que no posee la CPV. Las siguientes dos condiciones se cumplen, cualesquiera que sean los lenguajes L y X:

  

$$\left.\mbox{\it\begin{minipage}{8em} Operador estrella como supremo. \end{minipage}\/}\right] \mbox{\rm\begin{minipage}{24em}Si para todo $n\in I\!\!N$\space se tiene $K^nK^*+L=K^*+L$ , entonces $K^*+L=L$ .\end{minipage}}$$ : (26)

$$\mbox{\it Arden.\/}]\ \mbox{\rm Si $X=KX+L$\space entonces $X=K^* L$ .}$$ : (27)

En efecto, para la primera implicación, supongamos que $\sigma\in K^*$, y sea $m=\mbox{\it long\/}(\sigma)$ su longitud. Sea n>m. Puesto que $\sigma\in (K^*+L)$, necesariamente $\sigma\in (K^nK^*+L)$, pero todas las palabras de KⁿK^* son de longitud estrictamente mayor que la de $\sigma$, pues K no posee la CPV, por tanto a fortiori $\sigma\in L$. Así pues, $K^*\subset L$ y K^*+L=L. Ahora, para la segunda implicación, si se supone que X=KX+L entonces, al reiterar esta ecuación, resulta $X=K^{n+1}X+\left(\sum_{i=0}^n K^i\right)L$. Sea $\sigma\in\Sigma^*$, y sea $n\geq \mbox{\it long\/}(\sigma)$. Bajo esta condición, rigen las siguientes equivalencias:

$$\sigma\in X \ \ \Leftrightarrow\ \ \sigma\in \left(\sum_{i=0}^n K^i\right)L\ \ \Leftrightarrow\ \ \sigma\in K^*L.$$

Por tanto, X=K^*L.


Ahora bien, la relación de inclusión define un ``orden parcial'' en la clase ${\cal P}(\Sigma^*)$, y es tal que para cualesquiera dos lenguajes $K,L\in {\cal P}(\Sigma^*)$:

$$K\subset L\Leftrightarrow K\cup L=L.$$

Así pues, atendiendo únicamente a las operaciones definidas arriba se tiene que la relación

$$K\leq L\Leftrightarrow K+ L=L,$$

es un orden parcial en ${\cal P}(\Sigma^*)$ (que de hecho coincide con la inclusión de conjuntos).
Siguiente: Presentación formal Un nivel arriba: Expresiones regulares Anterior: Expresiones regulares