4
$\begingroup$

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
    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._2011-04-06
  • 0
    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!2011-04-06

1 Answers 1