×

Characterization of Glushkov automata. (English) Zbl 0952.68084

Summary: Glushkov’s algorithm computes a nondeterministic finite automaton without \(\varepsilon\)-transitions and with \(n+1\) states from a regular expression having \(n\) occurrences of letters. The aim of this paper is to give a set of necessary and sufficient conditions characterizing this automaton. Our characterization theorem is formulated in terms of directed graphs. Moreover, these conditions allow us to produce an algorithm of conversion of a Glushkov automaton into a regular expression of small size.

MSC:

68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)

Software:

LANGAGE; AUTOMATE; AG; AMoRE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.; A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974. · Zbl 0326.68005
[2] Berry, G.; Sethi, R., From regular expression to deterministic automata, Theoret. Comput. Sci., 48, 1, 117-126 (1986) · Zbl 0626.68043
[3] J. Berstel, Transductions and Context-free Languages, Teubner, Stuttgart, 1979.; J. Berstel, Transductions and Context-free Languages, Teubner, Stuttgart, 1979. · Zbl 0424.68040
[4] J. Berstel, Finite automata and rational languages, an introduction, in: J.-E. Pin (Ed.), Formal Properties of Finite Automata and Applications, Lecture Notes in Computer Science, vol. 386, Springer-Verlag, Berlin, 1989, pp. 2-14.; J. Berstel, Finite automata and rational languages, an introduction, in: J.-E. Pin (Ed.), Formal Properties of Finite Automata and Applications, Lecture Notes in Computer Science, vol. 386, Springer-Verlag, Berlin, 1989, pp. 2-14.
[5] Berstel, J.; Pin, J.-E., Local languages and the Berry-Sethi algorithm, Theoret. Comput. Sci., 155, 439-446 (1996) · Zbl 0872.68116
[6] Brüggemann-Klein, A., Regular expressions into finite automata, Theoret. Comput. Sci., 120, 1, 197-213 (1993) · Zbl 0811.68096
[7] P. Caron, AG: Manuel de l’utilisateur, Rapport LIR 96.09, Université de Rouen, France, 1996.; P. Caron, AG: Manuel de l’utilisateur, Rapport LIR 96.09, Université de Rouen, France, 1996.
[8] Caron, P., AG: A set of Maple packages for manipulating automata and finite semigroups, Software-Practice & Experience, 27, 8, 863-884 (1997)
[9] J.-M. Champarnaud, AUT: un langage pour la manipulation des automates et des semigroupes finis, in: D. Krob (Ed.), Actes des
((2^e\); J.-M. Champarnaud, AUT: un langage pour la manipulation des automates et des semigroupes finis, in: D. Krob (Ed.), Actes des
((2^e\)
[10] Champarnaud, J.-M.; Hansel, G., Automate, a computing package for automata and finite semigroups, J. Symbol, Comput., 12, 197-220 (1991) · Zbl 0804.68096
[11] C.-H. Chang, R. Paige, From regular expression to DFA’s using NFA’s, in: A. Apostolico, M. Crochemore, Z. Galil, U. Manber (Eds.), Proc. 3rd Annual Symp. on Combinatorial Pattern Matching, Tucson, AZ, Lecture Notes in Computer Science, vol. 664, Springer, Berlin, 1992, pp. 90-110.; C.-H. Chang, R. Paige, From regular expression to DFA’s using NFA’s, in: A. Apostolico, M. Crochemore, Z. Galil, U. Manber (Eds.), Proc. 3rd Annual Symp. on Combinatorial Pattern Matching, Tucson, AZ, Lecture Notes in Computer Science, vol. 664, Springer, Berlin, 1992, pp. 90-110.
[12] Eilenberg, S., Automata, Languages and Machines, vol. B (1976), Academic Press: Academic Press New York · Zbl 0359.94067
[13] Glushkov, V. M., The abstract theory of automata, Russian Math. Surveys, 16, 1-53 (1961) · Zbl 0104.35404
[14] J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, MA, 1979.; J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, MA, 1979. · Zbl 0426.68001
[15] V. Jansen, A. Potthoff, W. Thomas, U. Wermuth, A short guide to the AMoRE system (computing Automata, MOnoids and Regular Expressions), Technical Report 90.2, Aachener Informatik-Berichte, Ahornstr 55, D-5100 Aachen, 1990.; V. Jansen, A. Potthoff, W. Thomas, U. Wermuth, A short guide to the AMoRE system (computing Automata, MOnoids and Regular Expressions), Technical Report 90.2, Aachener Informatik-Berichte, Ahornstr 55, D-5100 Aachen, 1990.
[16] O. Matz, A. Miller, A. Potthoff, W. Thomas, E. Valkena, Report on the program AMoRE, Report, Institut für informatik und praktische mathematik, Christian-Albrechts Universität, Kiel, 1995.; O. Matz, A. Miller, A. Potthoff, W. Thomas, E. Valkena, Report on the program AMoRE, Report, Institut für informatik und praktische mathematik, Christian-Albrechts Universität, Kiel, 1995.
[17] R. McNaughton, H. Yamada, Regular expressions and state graphs for automata, IRA Trans. Electron. Comput. EC-9 (1) (1960) 39-47.; R. McNaughton, H. Yamada, Regular expressions and state graphs for automata, IRA Trans. Electron. Comput. EC-9 (1) (1960) 39-47. · Zbl 0156.25501
[18] Mirkin, B. G., An algorithm for constructing a base in a language of regular expressions, Eng. Cybernet., 5, 110-116 (1966)
[19] J.-L. Ponty, D. Ziadi, J.-M. Champarnaud, A new quadratic algorithm to convert a regular expression into an automaton, in: D. Raymond, D. Wood, S. Yu (Eds.), Automata Implementation: 1st Internat. Workshop on Implementing Automata, WIA’96, London, Ontario, Lecture Notes in Computer Science, vol. 1260, Springer, Berlin, 1997, pp. 109-119.; J.-L. Ponty, D. Ziadi, J.-M. Champarnaud, A new quadratic algorithm to convert a regular expression into an automaton, in: D. Raymond, D. Wood, S. Yu (Eds.), Automata Implementation: 1st Internat. Workshop on Implementing Automata, WIA’96, London, Ontario, Lecture Notes in Computer Science, vol. 1260, Springer, Berlin, 1997, pp. 109-119.
[20] Thompson, K., Regular expression search algorithm, Comm. ACM, 11, 6, 419-422 (1968) · Zbl 0164.46205
[21] B.W. Watson, A taxonomy of finite automata construction algorithms, Report, Department of Mathematics and Computing Science, Eindhoven University of Technology, The Netherlands, 1994.; B.W. Watson, A taxonomy of finite automata construction algorithms, Report, Department of Mathematics and Computing Science, Eindhoven University of Technology, The Netherlands, 1994.
[22] J.-L. Ponty, D. Ziadi,; 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.