Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A.V. Aho, J.E. Hopcroft, and J.D. Ullman. Data Structures and Algorithms. Addison-Wesley, Reading, MA, 1983.
V. Antimirov. Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci., 155:291–319, 1996.
D. Beauquier, J. Berstel, and P. Chrétienne. Éléments d’Algorithmique. Masson, Paris, 1992.
A. Brüggemann-Klein, Regular Expressions into Finite Automata. Theoret. Comput. Sci., 120 (1993), 197–213.
G. Berry and R. Sethi. From regular expressions to deterministic automata. Theoret. Comput. Sci., 48(1):117–126, 1986.
J.A. Brzozowski. Derivatives of regular expressions. J. Assoc. Comput. Mach., 11(4):481–494, 1964.
J.-M. Champarnaud and D. Ziadi, From C-Continuations to New Quadratic Algorithms for Automaton Synthesis. Intern. Journ. of Alg. Comp., to appear.
C.-H. Chang and R. Paige. From Regular Expressions to DFAs using Compressed NFAs, in Apostolico. Crochemore. Galil. and Manber. editors. Lecture Notes in Computer Science, 644(1992), 88–108.
V.M. Glushkov. The abstract theory of automata. Russian Mathematical Surveys, 16:1–53, 1961.
Ch. Hagenah and A. Muscholl, Computing ε-free NFA from Regular Expressions in O(nlog2(n)) Time, in: L. Prim et al. (eds.), MFCSé98, Lecture Notes in Computer Science, 1450 (1998), 277–285, Springer.
J. Hromkovič, S. Seibert and T. Wilke, Translating regular expressions into small ε-free nondeterministic finite automata, in: R. Reischuk (ed.), STACS’97, Lecture Notes in Computer Science, 1200 (1997), 55–66, Springer.
R.F. McNaughton and H. Yamada. Regular expressions and state graphs for automata. IEEE Transactions on Electronic Computers, 9:39–57, 1960.
B.G. Mirkin. An algorithm for constructing a base in a language of regular expressions. Engineering Cybernetics, 5:110–116, 1966.
R. Paige and R.E. Tarjan. Three partition refinement algorithms. SIAM J. Comput., 16(6), 1987.
J.-L. Ponty, D. Ziadi and J.-M. Champarnaud, A new Quadratic Algorithm to convert a Regular Expression into an Automaton, In: D. Raymond and D. Wood, eds., Lecture Notes in Computer Science, 1260 (1997) 109–119.
K. Thompson. Regular expression search algorithm. Comm. ACM, 11(6):419–422, 1968.
B.W. Watson. Taxonomies and Toolkit of Regular Languages Algorithms. PhD thesis, Faculty of mathematics and computing science, Eindhoven University of Technology, The Netherlands, 1995.
S. Yu. Regular languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, vol. I, 41–110. Springer-Verlag, Berlin, 1997.
D. Ziadi, J.-L. Ponty, and J.-M. Champarnaud. Passage d’une expression rationnelle à un automate fini non-déterministe. Journées Montoises (1995), Bull. Belg. Math. Soc., 4:177–203, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Champarnaud, JM., Ziadi, D. (2001). New Finite Automaton Constructions Based on Canonical Derivatives. In: Yu, S., Păun, A. (eds) Implementation and Application of Automata. CIAA 2000. Lecture Notes in Computer Science, vol 2088. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44674-5_7
Download citation
DOI: https://doi.org/10.1007/3-540-44674-5_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42491-8
Online ISBN: 978-3-540-44674-3
eBook Packages: Springer Book Archive