Siguiente: Puntos fijos de ecuaciones Un nivel arriba: Estructura algebraica de las Anterior: Estructura algebraica de las

Orden

Sea $\Sigma$ un alfabeto. En la clase de expresiones regulares $\mbox{\it ER\/}(\Sigma)$ introducimos la relación

$$\forall A,B:\ A\leq B\ \Leftrightarrow\ A+B\equiv B.$$

Tenemos con ésta, una relación reflexiva y transitiva. Esta relación aunque no es antisimétrica en $\mbox{\it ER\/}(\Sigma)$ sí lo es en el cociente $(\mbox{\it ER\/}(\Sigma)/\equiv)$ en donde, como ya vimos, coincide con la relación de orden de inclusión en los lenguajes formalmente regulares.

Proposición 3.1   Las siguientes relaciones son verdaderas:

1.

$\mbox{\bf0}\in \mbox{\it ER\/}(\Sigma)$ es el elemento mínimo, es decir, $\forall A\in \mbox{\it ER\/}(\Sigma):\ \mbox{\bf0}\leq A$.

2.

A posee la CPV si y sólo si $\mbox{\bf 1}\leq A$.

3.

$\forall A\in \mbox{\it ER\/}(\Sigma):\ \mbox{\bf 1}\leq A^*$.

4.

$\forall A,B\in \mbox{\it ER\/}(\Sigma):\ A\leq A+B$.

5.

$\forall A\in \mbox{\it ER\/}(\Sigma),\forall n\in I\!\!N:\ \mbox{\bf 1}+A+\cdots+A^n\leq A^*$.

6.

Si $A\leq B$ entonces $\forall C\in \mbox{\it ER\/}(\Sigma)$:

• $A\in\mbox{\it CPV\/}\ \Rightarrow\ B\in\mbox{\it CPV\/}$,
• $A+C\leq B+C$,
• $A\cdot C\leq B\cdot C$ y $C\cdot A\leq C\cdot B$,
• $A^*\leq B^*$.

En efecto, verifiquemos cada una de las aseveraciones:

1.

Como $\mbox{\bf0}$ es la unidad aditiva, $\mbox{\bf0}+ A=A$, por tanto, $\mbox{\bf0}\leq A$.

2.

Por inducción en la caracterización de las expresiones que poseen la CPV se ve que $A\in\mbox{\it CPV\/}\Leftrightarrow \mbox{\bf 1}+A=A$.

3.

Esta desigualdad se sigue inmediatamente de que A^* posee la CPV.

4.

Por ser la suma idempotente, A+ (A+B)=A+B, por tanto, $A\leq A+B$.

5.

Por la ec. (4.5) $\forall A\in \mbox{\it ER\/}(\Sigma),\forall n\in I\!\!N$ se tiene:

$$A^* + A^{n+1}A^*=\left(\sum_{i=0}^n A^n + A^{n+1}A^*\right) + A^{n+1}A^*=\sum_{i=0}^n A^n + A^{n+1}A^*=A^*$$

luego

$$\mbox{\bf 1}+A+\cdots+A^n+ A^*=\mbox{\bf 1}+A+\cdots+A^n+ (A^{n+1}A^*+A^*)=(A^*+A^*)=A^*,$$

por tanto, $\mbox{\bf 1}+A+\cdots+A^n\leq A^*$.

6.

Si $A\leq B$ entonces A+ B=B, luego $\forall C\in \mbox{\it ER\/}(\Sigma)$:

• como B=(A+B), $B\in\mbox{\it CPV\/}$,
• (A+C)+(B+C)=(A+B)+C=B+C, por tanto, $A+C\leq B+C$,
• $A\cdot C+ B\cdot C=(A+ B)\cdot C=B\cdot C$, por tanto, $A\cdot C\leq B\cdot C$,
• Ya que $A\leq B$ y $B\leq B^*$ se tiene $A\leq B^*$. Luego, $\forall n:\ \left(\sum_{i=0}^{n-1} A^i\right)\leq B^*$. En consecuencia, A^*+ B^*=AⁿA^*+ B^*. Si A no posee la CPV, del último de los axiomas enlistados en la tabla (4.1) se sigue $A^*\leq B^*$. Si A posee la CPV, escribamos $A=\mbox{\bf 1}+A_1$ donde A₁ no posee la CPV. Entonces, $A^*= (\mbox{\bf 1}+A_1)^*= A_1^*\leq B^*$.

Tenemos pues, en conclusión, que las operaciones regulares son monótonas respecto a la relación de orden.
Siguiente: Puntos fijos de ecuaciones Un nivel arriba: Estructura algebraica de las Anterior: Estructura algebraica de las