# Enhancing the monoid structure over a finite alphabet to prove Arden's rule

Suppose you have a finite-state, deterministic automaton, that you wish to convert to a regular expression. A common method, perhaps easier to apply by hand that Yamada's algorithm, is to reduce the automaton to a set of equalities between subsets of $A^*$, where $A$ is a finite alphabet (finite set), and $A^* = \bigcup_{n=0}^\infty A^n$.

A very useful lemma in solving these equations is Arden's rule, which states that the smallest subset $X \subset A^*$ satisfying the equation $X=K.X|L$ is $K^*L$, where $K, L \subset A^*$, $.$ denotes concatenation (product), and $|$ denotes a choice (union).

Now, consider the following, completely formal equalities:

\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}

Except for the first equality, all the other ones are based on undefined operations, but I've been wondering: since this type of calculations is valid in certain algebras, is there a way to define an algebraic structure over $A^*$ which would legitimate the previous calculations?

There might not be any, but I have the feeling that there's more to this than a mere coincidence.

Thanks for your ideas!

• You can use generating functions (in non-commuting variables). Something like this is done in the relevant section of Stanley's Enumerative Combinatorics Vol. II. – Qiaochu Yuan Apr 6 '11 at 21:19
• I was able to find a copy at the library, and you're right! It mentions factorization in free monoids in section 4.7.9. Thanks! – Clément Apr 6 '11 at 21:42

Your intuition is right. To make it formal, you have to work with rational series with noncommutative variables and coefficients in $\mathbf{Z}$. Here is a good reference on this topic: