×

Partial derivatives of regular expressions and finite automaton constructions. (English) Zbl 0872.68120

Summary: We introduce a notion of partial derivative of a regular expression and apply it to finite automaton constructions. The notion is a generalization of the known notion of word derivative due to J. A. Brzozowski [J. Assoc Comput. Mach. 11, 481-494 (1964; Zbl 0225.94044)]: partial derivatives are related to non-deterministic finite automata (NFA’s) in the same natural way as derivatives are related to deterministic ones (DFA’s). We give a constructive definition of partial derivatives and prove several facts, in particular: (1) any derivative of a regular expression \(r\) can be represented by a finite set of partial derivatives of \(r\); (2) the set of all partial derivatives of \(r\) is finite and its cardinality is less than or equal to one plus the number of occurrences of letters from \({\mathcal A}\) appearing in \(r\); (3) any partial derivative of \(r\) is either a regular unit, or a subterm of \(r\), or a concatenation of several such subterms. These theoretical results lead us to a new algorithm for turning regular expressions into relatively small NFA’s and allow us to provide certain improvements to Brzozowski’s algorithm for constructing DFA’s. We also report on a prototype implementation of our NFA construction and present several examples.

MSC:

68Q45 Formal languages and automata
68W15 Distributed algorithms

Citations:

Zbl 0225.94044

Software:

OBJ3
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Antimirov, V. M., Rewriting regular inequalities, December 1994, (Proc. FCT’95, to be presented at the conf. Fundamentals of Computation Theory (August, 1995)), in:
[2] Antimirov, V. M., Partial derivatives of regular expressions and finite automata constructions, (Mayr, E. W.; Puech, C., 12th Annual Symp. on Theoretical Aspects of Computer Science. Proceedings. 12th Annual Symp. on Theoretical Aspects of Computer Science. Proceedings, Lecture Notes in Computer Science, Vol. 900 (1995), Springer: Springer Berlin), 455-466 · Zbl 1379.68209
[3] Antimirov, V. M.; Mosses, P. D., Rewriting extended regular expressions, Theoret. Comput. Sci., 143, 51-72 (1995) · Zbl 0873.68104
[4] Benanav, D.; Kapur, D.; Narendran, P., Complexity of matching problems, J. Symbolic Comput., 3, 1-2, 203-216 (1987) · Zbl 0638.68036
[5] Berry, G.; Sethi, R., From regular expressions to deterministic automata, Theoretical Comput. Sci., 48, 117-126 (1986) · Zbl 0626.68043
[6] Berstel, J., Finite automata and rational languages. an introduction, (Pin, J., Finite Automata and Applications. Finite Automata and Applications, Lecture Notes in Computer Science, Vol. 386 (1987), Springer: Springer Berlin), 2-14
[7] Brüggemann-Klein, A., Regular expressions into finite automata, Theoret. Comput. Sci., 120, 197-213 (1993) · Zbl 0811.68096
[8] Brzozowski, J. A., Derivatives of regular expressions, J. ACM, 11, 481-494 (1964) · Zbl 0225.94044
[9] Brzozowski, J. A.; Leiss, E. L., On equations for regular languages, finite automata, and sequential networks, Theoret. Comput. Sci., 10, 19-35 (1980) · Zbl 0415.68023
[10] Chang, C.-H.; Paige, R., From regular expressions to DFA’s using compressed NFA’s, (Apostolico, A.; Crochemore, M.; Galil, Z.; Manber, U., Combinatorial Pattern Matching. Proceedings. Combinatorial Pattern Matching. Proceedings, Lecture Notes in Computer Science, Vol. 644 (1992), Springer: Springer Berlin), 88-108 · Zbl 0912.68105
[11] Conway, J. H., Regular Algebra and Finite Machines (1971), Chapman and Hall: Chapman and Hall London · Zbl 0231.94041
[12] Dershowitz, N.; Jouannaud, J.-P., Rewrite systems, (van Leeuwen, J., Handbook of Theoretical Computer Science, Vol. B (1990), Elsevier: Elsevier Amsterdam), and MIT Press, Cambridge, MA · Zbl 0900.68283
[13] Ginzburg, A., A procedure for checking equality of regular expressions, J. ACM, 14, 2, 355-362 (1967) · Zbl 0155.34501
[14] Glushkov, V. M., The abstract theory of automata, Russian Math. Surveys, 16, 1-53 (1961) · Zbl 0104.35404
[15] Goguen, J. A.; Meseguer, J., Order-sorted algebra I: Equational deduction for multiple inheritance, overloading, exceptions and partial operations, Theoret. Comput. Sci., 105, 217-273 (1992) · Zbl 0778.68056
[16] Goguen, J. A.; Winkler, T., Introducing OBJ3, (Technical Report SRI-CSL-88-9 (1988), Computer Science Lab., SRI International)
[17] Goldberg, R. M., Finite state automata from regular expression trees, Computer J., 36, 7, 623-630 (1993)
[18] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[19] Krob, D., Differentiation of K-rational expressions, Internat. J. Algebra Comput., 2, 1, 57-87 (1992) · Zbl 0785.68065
[20] Kucherov, G.; Rusinowitch, M., Complexity of testing ground reducibility for linear word rewriting systems with variables, (Proc. 4th Internat. Workshop on Conditional and Typed Term Rewriting Systems. Proc. 4th Internat. Workshop on Conditional and Typed Term Rewriting Systems, Jerusalem (Israel) (July 1994)), (To appear in the LNCS series) · Zbl 0998.68529
[21] Kucherov, G.; Rusinowitch, M., On Ground-Reducibility Problem for word rewriting systems with variables, (Deaton, E.; Wilkerson, R., Proc. 1994 ACMISIGAPP Symp. on Applied Computing. Proc. 1994 ACMISIGAPP Symp. on Applied Computing, Phoenix (USA), 1994 (1995), ACM-Press: ACM-Press New York) · Zbl 0998.68529
[22] McNaughton, R.; Yamada, H., Regular expressions and state graphs for automata, IEEE Trans. on Electronic Computers, 9, 1, 39-47 (1960) · Zbl 0156.25501
[23] Mizoguchi, Y.; Ohtsuka, H.; Kawahara, Y., A symbolic calculus of regular expressions, Bull. Inform. Cybernet., 22, 3-4, 165-170 (1987) · Zbl 0641.68079
[24] Myhill, J., Finite automata and the representation of events, (Technical Report WADD TR-57-624 (1957), Wright Patterson AFB: Wright Patterson AFB Ohio) · Zbl 0122.01102
[25] Nerode, A., Linear automaton transformations, (Proc. AMS, 9 (1958)), 541-544 · Zbl 0089.33403
[26] Perrin, D., Finite automata, (van Leeuwen, J., Handbook of Theoretical Computer Science, Vol B (1990), Elsevier: Elsevier Amsterdam), and MIT Press, Cambridge, MA · Zbl 0336.94033
[27] Rabin, M. O.; Scott, D., Finite automata and their decision problems, IBM J. Res. Development, 3, 2, 114-125 (1959) · Zbl 0158.25404
[28] Redko, V. N., On defining relations for the algebra of regular events, Ukrain. Mat. Zh., 16, 120-126 (1964)
[29] Salomaa, A., Theory of Automata (1969), Pergamon: Pergamon Oxford · Zbl 0193.32901
[30] Sippu, S.; Soisalon-Soininen, E., Parsing Theory. Vol. 1: Languages and Parsing, (EATCS Monographs on Theoretical Computer Science (1988), Springer: Springer Berlin) · Zbl 0651.68007
[31] Thompson, K., Regular expression search algorithms, Comm. ACM, 11, 6, 419-422 (1968) · Zbl 0164.46205
[32] Watson, B. W., A taxonomy of finite automata construction algorithms, (Computing Science Note 93/43 (1993), Eindhoven University of Technology: Eindhoven University of Technology The Netherlands) · Zbl 0858.68026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.