Sea
un alfabeto. En la clase de expresiones regulares
introducimos la relación
Tenemos con ésta, una relación reflexiva y transitiva. Esta relación aunque no es antisimétrica en
sí lo es en el cociente
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.
es el elemento mínimo, es decir,
.
2.
A posee la CPV si y sólo si
.
3.
.
4.
.
5.
.
6.
Si
entonces
:
,
,
y
,
.
En efecto, verifiquemos cada una de las aseveraciones:
1.
Como
es la unidad aditiva,
,
por tanto,
.
2.
Por inducción en la caracterización de las expresiones que poseen la CPV se ve que
.
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, .
Ya que
y
se tiene .
Luego,
.
En consecuencia,
A*+ B*=AnA*+ B*. Si A no posee la CPV, del último de los axiomas enlistados en la tabla (4.1) se sigue
.
Si A posee la CPV, escribamos
donde A1 no posee la CPV. Entonces,
.