Abstract
The notion of expression derivative due to Brzozowski leads to the construction of a deterministic automaton from an extended regular expression, whereas the notion of partial derivative due to Antimirov leads to the construction of a non-deterministic automaton from a simple regular expression. In this paper, we generalize Antimirov partial derivatives to regular expressions extended to complementation and intersection. For a simple regular expression with n symbols, Antimirov automaton has at most n + 1 states. As far as an extended regular expression is concerned, we show that the number of states can be exponential.
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
Antimirov, V.: Partial derivatives of regular expressions and finite automaton constructions. Theoretical Computer Science 155, 291–319 (1996)
Berry, G., Sethi, R.: From regular expressions to deterministic automata. Theoretical Computer Science 48(1), 117–126 (1986)
Brzozowski, J.A.: Derivatives of regular expressions. Journal of the Association for Computing Machinery 11(4), 481–494 (1964)
Champarnaud, J.M., Ponty, J.L., Ziadi, D.: From regular expressions to finite automata. International Journal of Computational Mathematics 72, 415–431 (1999)
Champarnaud, J.M., Ziadi, D.: Canonical derivatives, partial derivatives, and finite automaton constructions. Theoretical Computer Science 239(1), 137–163 (2002)
Ellul, K., Krawetz, B., Shallit, J., Wang, M.: Regular expressions: New results and open problems. Journal of Automata, Languages and Combinatorics 10(4), 407–437 (2005)
Gelade, W.: Succinctness of regular expressions with interleaving, intersection and counting. Theoretical Computer Science 411(31-33), 2987–2998 (2010)
Gelade, W., Neven, F.: Succinctness of the complement and intersection of regular expressions. In: Albers, S., Weil, P. (eds.) STACS. Dagstuhl Seminar Proceedings, vol. 08001, pp. 325–336 (2008)
Glushkov, V.M.: The abstract theory of automata. Russian Mathematical Surveys 16, 1–53 (1961)
Kleene, S.: Representation of events in nerve nets and finite automata. Automata Studies Annual Mathematical Studies 34, 3–41 (1956)
Leiss, E.: Constructing a finite automaton for a given regular expression. SIGACT News 12, 81–87 (1980)
McNaughton, R.F., Yamada, H.: Regular expressions and state graphs for automata. IEEE Transactions on Electronic Computers 9, 39–57 (1960)
Myhill, J.: Finite automata and the representation of events. Wright Air Development Command Technical Report 57-624, 112–137 (1957)
Nerode, A.: Linear automata transformation. In: Proceedings of AMS, vol. 9, pp. 541–544 (1958)
Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM Journal of Research and Development 3(2), 115–125 (1959)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Caron, P., Champarnaud, JM., Mignot, L. (2011). Partial Derivatives of an Extended Regular Expression. In: Dediu, AH., Inenaga, S., Martín-Vide, C. (eds) Language and Automata Theory and Applications. LATA 2011. Lecture Notes in Computer Science, vol 6638. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21254-3_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-21254-3_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21253-6
Online ISBN: 978-3-642-21254-3
eBook Packages: Computer ScienceComputer Science (R0)