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!

  • 1
    $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Apr 6 '11 at 21:19
  • $\begingroup$ 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! $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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