Supongamos que tenemos un estado finito determinista de los autómatas, que desea convertir a una expresión regular. Un método común, tal vez más fácil de aplicar con la mano que Yamada algoritmo, es reducir el autómata a un conjunto de igualdades entre los subconjuntos de a $A^*$ donde $A$ es un alfabeto finito finito (set), y $A^* = \bigcup_{n=0}^\infty A^n$.
Una muy útil lema en la solución de estas ecuaciones se Arden de la norma, la cual establece que el más pequeño subconjunto $X \subset A^*$ satisfacer la ecuación de $X=K.X|L$$K^*L$, donde $K, L \subset A^*$, $.$ denota la concatenación (producto), y $|$ denota una elección (de la unión).
Ahora, considere el siguiente, completamente formal igualdades:
$$ \begin{align} X &= KX+L\\ &= L + KX\\ X - KX &= L\\ (1-K)X &= L\\ X &= \frac1{1-K} L\\ &= \left(\sum_{n=0}^{\infty} K^n\right) L\\ &= K^*L \end{align} $$
Excepto para la primera igualdad, todos los demás se basan en indefinidos de operaciones, pero me he estado preguntando: ya que este tipo de cálculos es válida en ciertas álgebras, hay una manera de definir una estructura algebraica $A^*$ que sería legítimo de los cálculos anteriores?
No hay ninguno, pero tengo la sensación de que hay más a esto que una mera coincidencia.
Gracias por tus ideas!
