×

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
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Antimirov, V.M., Rewriting regular inequalities, December 1994, (), in:
[2] Antimirov, V.M., Partial derivatives of regular expressions and finite automata constructions, (), 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, (), 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, (), 88-108 · Zbl 0912.68105
[11] Conway, J.H., Regular algebra and finite machines, (1971), Chapman and Hall London · Zbl 0231.94041
[12] Dershowitz, N.; Jouannaud, J.-P., Rewrite systems, (), 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, ()
[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 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, (), (To appear in the LNCS series) · Zbl 0998.68529
[21] Kucherov, G.; Rusinowitch, M., On ground-reducibility problem for word rewriting systems with variables, () · 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, () · Zbl 0122.01102
[25] Nerode, A., Linear automaton transformations, (), 541-544 · Zbl 0089.33403
[26] Perrin, D., Finite automata, (), 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 Oxford · Zbl 0193.32901
[30] Sippu, S.; Soisalon-Soininen, E., Parsing theory. vol. 1: languages and parsing, () · 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, () · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.