Glushkov Construction For Series: The Non Commutative Case
Pascal Caron, Marianne Flouret · International Journal of Computer Mathematics · 2003
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.