Glushkov Construction For Series: The Non Commutative Case

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 give an extension of the Glushkov algorithm for the multiplicity case in a non commutative semiring. Next, we give four equivalent extended step by step algorithms.

Keywords:

• Automata With Multiplicities
• Glushkov Automata
• Rational Series