We present an extension to multiplicities of a classical algorithm for computing a boolean automaton from a regular expression. The Glushkov construction computes an automaton with n + 1 states from a regular expression with n occurences of letters. We show that the Glushkov algorithm still suits to the multiplicity case. Next, we give three equivalent extended step by step algorithms.
['Pascal Caron', 'Marianne Flouret']
Glushkov Construction for Multiplicities