×

Canonical derivatives, partial derivatives and finite automaton constructions. (English) Zbl 1061.68109

Summary: Let \(E\) be a regular expression. Our aim is to establish a theoretical relation between two well-known automata recognizing the language of \(E,\) namely the position automaton \(P_{E}\) constructed by Glushkov or McNaughton and Yamada, and the equation automaton \(E_{E}\) constructed by Mirkin or Antimirov. We define the notion of c-derivative (for canonical derivative) of a regular expression \(E\) and show that if \(E\) is linear then two Brzozowski’s derivatives of \(E\) are aci-similar if and only if the corresponding c-derivatives are identical. It allows us to represent the Berry-Sethi’s set of continuations of a position by a unique c-derivative, called the c-continuation of the position. Hence the definition of \(C_{E},\) the c-continuation automaton of \(E,\) whose states are pairs made of a position of \(E\) and of the associated c-continuation. If states are viewed as positions, \(C_{E}\) is isomorphic to \(P_{E}.\) On the other hand, a partial derivative, as defined by Antimirov, is a class of c-derivatives for some equivalence relation, thus \(C_{E}\) reduces to \(E_{E}.\) Finally \(C_{E}\) makes it possible to go from \(P_{E}\) to \(E_{E},\) while this cannot be achieved directly (from the state graphs). These theoretical results lead to an \(O(| E|^{2})\) space and time algorithm to compute the equation automaton, where \(| E|\) is the size of the expression. This is the complexity of the most efficient constructions yielding the position automaton, while the size of the equation automaton is not greater and generally much smaller than the size of the position automaton.

MSC:

68Q70 Algebraic theory of languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., Data Structures and Algorithms (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0307.68053
[2] Antimirov, V., Partial derivatives of regular expressions and finite automaton constructions, Theoret. Comput. Sci., 155, 291-319 (1996) · Zbl 0872.68120
[3] Beauquier, D.; Berstel, J.; Chrétienne, P., Éléments d’Algorithmique (1992), Masson: Masson Paris
[4] Berry, G.; Sethi, R., From regular expressions to deterministic automata, Theoret. Comput. Sci., 48, 1, 117-126 (1986) · Zbl 0626.68043
[5] Brzozowski, J. A., Derivatives of regular expressions, J. Assoc. Comput. Mach., 11, 4, 481-494 (1964) · Zbl 0225.94044
[6] J.-M. Champarnaud, D. Ziadi, From C-continuations to new quadratic algorithms for automaton synthesis, Internat. J. Algebra Comput. 11 (6) (2001) 707-735.; J.-M. Champarnaud, D. Ziadi, From C-continuations to new quadratic algorithms for automaton synthesis, Internat. J. Algebra Comput. 11 (6) (2001) 707-735. · Zbl 1024.68065
[7] J.-M. Champarnaud, D. Ziadi, From Mirkin’s prebases to Antimirov’s word partial derivatives, Fund. Inform. 45(3) (2001) 195-205.; J.-M. Champarnaud, D. Ziadi, From Mirkin’s prebases to Antimirov’s word partial derivatives, Fund. Inform. 45(3) (2001) 195-205. · Zbl 0976.68098
[8] Glushkov, V. M., The abstract theory of automata, Russian Math. Surveys, 16, 1-53 (1961) · Zbl 0104.35404
[9] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[10] S. Kleene, Representation of events in nerve nets and finite automata, Automata Studies Annals of Mathematics Studies vol. 34, 1956, Princeton University Press, Princeton NJ, pp. 3-41.; S. Kleene, Representation of events in nerve nets and finite automata, Automata Studies Annals of Mathematics Studies vol. 34, 1956, Princeton University Press, Princeton NJ, pp. 3-41.
[11] McNaughton, R. F.; Yamada, H., Regular expressions and state graphs for automata, IEEE Trans. Electron. Comput., 9, 39-57 (1960) · Zbl 0156.25501
[12] Mirkin, B. G., An algorithm for constructing a base in a language of regular expressions, Eng. Cybernet., 5, 110-116 (1966)
[13] Paige, R.; Tarjan, R. E., Three partition refinement algorithms, SIAM J. Comput., 16, 6, 973-989 (1987) · Zbl 0654.68072
[14] S. Yu, Regular languages, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, vol. I, Words, Languages, Grammars, Springer, Berlin, 1997, pp. 41-110.; S. Yu, Regular languages, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, vol. I, Words, Languages, Grammars, Springer, Berlin, 1997, pp. 41-110.
[15] Ziadi, D.; Ponty, J.-L.; Champarnaud, J.-M., Passage d’une expression rationnelle à un automate fini non-déterministe, Bull. Belg. Math. Soc., 4, 177-203 (1997) · Zbl 0915.68123
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.