Siguiente: Matrices de expresiones regulares Un nivel arriba: Estructura algebraica de las Anterior: Orden

Puntos fijos de ecuaciones lineales

Dadas dos expresiones regulares $A,B\in\mbox{\it ER\/}(\Sigma)$ sea $P_{A,B}=\{X\in\mbox{\it ER\/}(\Sigma)\vert X=AX+B\}$ el conjunto de expresiones regulares que son puntos fijos de la ``función'' $X\mapsto AX+B$.

Observación 3.1   La siguientes relaciones son verdaderas:

1.

La expresión A^*B está en P_A,B.

2.

A^*B es una cota inferior de P_A,B. Es decir, $\forall X\in\mbox{\it ER\/}(\Sigma):\ X\in P_{A,B}\Rightarrow A^*B\leq X$.

3.

Si A no posee la CPV, entonces P_A,B consta del único elemento A^*B. Es decir, A^*B es el único punto fijo de la ``transformación lineal'' $X\mapsto AX+B$.

En efecto:

1.

$A^*B=(\mbox{\bf 1}+AA^*)B=A(A^*B) + B.$ Así pues, $A^*B\in P_{A,B}$.

2.

Si $X\in P_{A,B}$ entonces X=AX+B y, mediante sustituciones sucesivas, se tiene

$$\forall n:\ X=A^{n+1} X+(A^n+A^{n-1}+\cdots +A+\mbox{\bf 1})B,$$

y por tanto $\forall n:X\geq A^nB$. Consecuentemente, $X\geq A^*B$.

3.

Esto es un replanteamiento del resultado formulado en la ec. (4.16).

Resumimos todo lo anterior, aunque sea de manera reiterada, en el siguiente

Lema 3.1 (Arden)   $\forall A,B\in\mbox{\it ER\/}(\Sigma):\ \ \mbox{\bf 1}\not\leq A\ \ \Rightarrow\ \ \left(X=AX+B\ \Leftrightarrow\ X=A^*B\right).$

La suposición de que A no posea la CPV es importante. Por ejemplo, si A poseyera la CPV y B fuese cualquier expresión regular, entonces siempre que $X\geq B$ se tendrá: $X=X+B=\mbox{\bf 1}X+B$. Sin embargo, no necesariamente se tendrá que $X=\mbox{\bf 1}^*B=B$.
Siguiente: Matrices de expresiones regulares Un nivel arriba: Estructura algebraica de las Anterior: Orden