Weighted automata were designed by M.-P. Schützenberger to recognize languages beyond regular languages. Nowadays, the functions realized by these devices are studied; they represent fuzzy computations, probabilities, cost functions, execution times, etc. depending on the nature of the weights. Epsilon-transitions are a common feature of finite automata and their extension to weighted automata seems to be straightforward. Yet, they can lead to an infinite amount of accepting runs for a given input, and, therefore, the study of the behaviour of such machines is not trivial. Finally, we focus on the problem of the extension of the well-known Thompson automaton in the weighted case that leads to some unexpected outcomes.

Joint work with Jacques Sakarovitch.