Study of a generalisation of the removal of ε-transitions from a non-deterministic automaton.

A non-deterministic automaton transitions from one state to the next when it reads an input symbol. It is common to also allow the automaton to transition without input. These so-called ε-transitions are useful, for example, when one wants to transform a regular expression to a non-deterministic automaton. These ε-transitions are not necessary, and can be removed: for every non-deterministic automaton with ε-transitions there is a non-deterministic automaton without ε-transitions which recognises the same language.

In this paper we study a generalisation of this ε-transition removal procedure which makes use of monads and the Kleisli category. Weighted automata over positive semirings fit our framework, but weighted automata over the reals do not, and cannot fit any framework similar to ours.