Nous présentons un algorithme de calcul de l'automate préfixe d'un automate. Les automates que nous considérons sont des automates non déterministes, étiquetés sur les mots et avec ε-transitions. L'automate préfixe d'un automate A a les propriétés suivantes. Il a le même graphe que A, chaque chemin acceptant a la même étiquette que dans A. Pour chaque état q, le plus long préfixe commun des étiquettes des chemins de q à un état initial ou final est vide. L'intérêt du calcul de l'automate préfixe d'un automate est qu'il constitue la première étape dans la minimisation des transducteurs séquentiels.
L'algorithme que nous décrivons a la même complexité en temps qu'un autre algorithme dû à Mohri mais notre algorithme accepte les automates qui ont des cycles étiquetés par le mot vide. La complexité est O((P+1)×|E|), où E est l'ensemble des flèches et P la longueur maximale des plus longs préfixes communs des étiquettes des chemins d'un état donné à un état initial ou final
We present an algorithm for computating the prefix of an automaton. Automata considered are non-deterministic, labelled on words, and can have ε-transitions. The prefix automaton of an automaton A has the following properties. It has the same graph as A. Each accepting path has the same label as in A. For each state q, the longest common prefix of the labels of all paths going from q to an initial of final state is empty. The interest of the computation of the prefix of an automaton is that it is the first step of the minimization of sequential transducers.
The algorithm that we describe has the same worst time complexity as another algorithm from Mohri but our algorithm allows automata that have empty labelled cycles. It operates in O((P+1)×|E|), where E is the set of edges and P the size of the longest common prefixes of the labels of paths leaving each state of the automaton and ending in an initial or final state.