From Glushkov WFAs to \mathbb{K}-Expressions

Abstract

We take an active interest in the problem of conversion of a Weighted Finite Automaton (WFA) into a \mathbb{K}-expression. The known algorithms give an exponential size expression in the number of states of the given automaton. We study the McNaughton-Yamada algorithm in the case of multiplicities and then we show that the resulting \mathbb{K}-expression is in the Star Normal Form (SNF) defined by Brüggemann-Klein [3]. The Glushkov algorithm computes an (n + 1)-state automaton from an expression having n occurrences of letters even in the multiplicity case [5]. We reverse this procedure and get a linear size \mathbb{K}-expression from a Glushkov WFA. A characterization of Glushkov WFAs which are not in SNF is given. This characterization allows us to emphasize a normal form for \mathbb{K}-expressions. As for SNF in the boolean case, we show that every \mathbb{K}-expression has an equivalent one in normal form having the same Glushkov WFA. We end with an algorithm giving a small normal form \mathbb{K}-expression from a Glushkov WFA.