A New Family of Regular Operators Fitting with the Position Automaton Computation

Pascal Caron (1, 2) , Jean-Marc Champarnaud (3) , Ludovic Mignot (2, 3)

1 CA - LITIS - Equipe Combinatoire et algorithmes
2 UNIROUEN - Université de Rouen Normandie
3 LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes

The aim of this paper is to define a new family of regular operators fitting with the construction of the position automaton. These new operators support the computation of the four Glushkov functions (Null, First, Last and Follow), which allows the conversion of an extended expression with n symbol occurrences into a position automaton with n + 1 states.

Keywords: Regular Expression; Regular Language; Empty Word; Linear Expression; Regular Operator

Domains: Computer Science [cs]

Pascal Caron, Jean-Marc Champarnaud, Ludovic Mignot. A New Family of Regular Operators Fitting with the Position Automaton Computation. SOFSEM 2009: Theory and Practice of Computer Science, 35th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlýn, Czech Republic, January 24-30, 2009. Proceedings, 2009, Czech Republic. pp.645--655, ⟨10.1007/978-3-540-95891-8_57⟩. ⟨hal-02335305⟩