New finite automaton constructions based on canonical derivatives. (English) Zbl 0989.68077

Yu, Sheng (ed.) et al., Implementation and application of automata. 5th international conference, CIAA 2000, London, Ontario, Canada, July 24-25, 2000. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 2088, 94-104 (2001).
Summary: Two classical constructions to convert a regular expression into a finite non-deterministic automaton provide complementary advantages: the notion of position of a symbol in an expression, introduced by Glushkov and McNaugthon-Yamada, leads to an efficient computation of the position automaton (there exist quadratic space and time implementations w.r.t. the size of the expression), whereas the notion of derivative of an expression w.r.t. a word, due to Brzozowski, and generalized by Antimirov, yields a small automaton. The number of states of this automaton, called the equation automaton, is less than or equal to the number of states of the position automaton, and in practice it is generally much smaller. So far, algorithms to build the equation automaton, such as Mirkin’s or Antimirov’s ones, have a high space and time complexity. The aim of this paper is to present new theoretical results allowing to compute the equation automaton in quadratic space and time, improving by a cubic factor Antimirov’s construction. These results lay on the computation of a new kind of derivative, called canonical derivative, which makes it possible to connect the notion of continuation in a linear expression due to Berry and Sethi, and the notion of partial derivative of a regular expression due to Antimirov. A main interest of the notion of canonical derivative is that it leads to an efficient computation of the equation automaton via a specific reduction of the position automaton.
For the entire collection see [Zbl 0968.00056].


68Q45 Formal languages and automata
Full Text: Link