next up previous contents
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

\begin{displaymath}\forall A,B:\ A\leq B\ \Leftrightarrow\ A+B\equiv B.\end{displaymath}

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:

\begin{displaymath}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^*\end{displaymath}

luego

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

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)$:
Tenemos pues, en conclusión, que las operaciones regulares son monótonas respecto a la relación de orden.
next up previous contents
Siguiente: Puntos fijos de ecuaciones Un nivel arriba: Estructura algebraica de las Anterior: Estructura algebraica de las
Guillermo Morales-Luna
2000-06-27