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.
Date and Venue
Room FC6029 (CS Bldg., FCUP) and Online
IRIF, CNRS-U. Paris Cité & LTCI, Télécom Paris
Semigroups, Automata and Languages