Affiliations: LACL, EA 4912, Université Paris-Est Créteil (UPEC), Créteil, France. mdahmoune@yahoo.fr, mohamed.dahmoune@u-pec.fr | LMRS, UMR 6085 CNRS, Normandie Université, Rouen, France. elhoucein.elabdalaoui@univ-rouen.fr | LITIS, EA 4108, Normandie Université, Rouen, France. djelloul.ziadi@univ-rouen.fr
Note: [] I thank Saïd Abdeddaïm who proposed me to work with D. Ziadi. Address for correspondence: LACL, EA 4912, Université Paris-Est Créteil (UPEC), Créteil, France
Note: [] We would like to express thanks to anonymous referee for his/her helpful comments and suggestions, which significantly contributed to improve the quality of our paper.
Note: [] Special thanks to Alexis Bès, Patrick Cégielski, Jean-Marc Champarnaud and Yuri Matiyasevich.
Abstract: In this paper we apply the concept of common follow sets (CFS) of a regular expression to homogeneous finite state automaton. Based on this concept and using particular binary trees, we devise an efficient algorithm to reduce (minimize) the number of transitions of the automaton recognizing the language L(En) denoted by the regular expression $E_n = (1 + \epsiv) \cdot (2 + \epsiv) \cdot (3 + \epsiv) \dots (n+\epsiv)$. Experiments reveal that for small values of n, all ε-free NFAs with n+1 states and with a minimum number of transitions for L(En) are exactly those obtained by our construction. Also, the produced ε-free NFA is asymptotically minimal, in the sense that the number of transitions is equivalent to n(log2 n)2 which corresponds in the same time to the upper and the lower bound. We conjecture that our construction is not only a reduction but a minimization for L(En).
