Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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:

J. Berstel and C. Reutenauer, Noncommutative rational series with applications. Encyclopedia of Mathematics and its Applications, 137. Cambridge University Press, Cambridge, 2011. xiv+248 pp. ISBN: 978-0-521-19022-0

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.