The topic of this talk is the transformation of rational expressions into finite automata, a much laboured subject indeed. The starting point is the derived term automaton (aka partial derivative, or Antimirov, automaton) of a rational (or regular) expression, a modification of  Brzozowski derivative automaton. By taking a shifted perspective, I shall present a construction of this automaton based on a sole induction on the depth of the expression and that does not make reference to any operation of derivation of the expression. It is particularly well-suited to the case of weighted rational expressions and it broadens the scope of the method to (weighted) expressions over non free monoids.

Joint work with Sylvain Lombardy.