Sabine Broda, António Machiavelo, Nelma Moreira and Rogério Reis

**Abstract.** In this paper, the relation between the Glushkov automaton (*A*_{pos}) and the partial derivative automaton (*A*_{pd}) of a given regular expression, in terms of transition complexity, is studied. The average transition complexity of *A*_{pos} was proved by Nicaud to be linear in the size of the corresponding expression. This result was obtained using an upper bound of the number of transitions of *A*_{pos}. Here we present a new quadratic construction of *A*_{pos} that leads to a more elegant and straightforward implementation, and that allows the exact counting of the number of transitions. Based on that, a better estimation of the average size is presented. Asymptotically, and as the alphabet size grows, the number of transitions per state is on average 2.

Broda *et al.* computed an upper bound for the ratio of the number of states of *A*_{pd} to the number of states of *A*_{pos}, which is about 1/2 for large alphabet sizes. Here we show how to obtain an upper bound for the number of transitions in *A*_{pd}, which we then use to get an average case approximation. Some experimental results are presented that illustrate the quality of our estimate.