Regular expressions for some Petri net languages for the producer/consumer problem
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2020.3.08Keywords:
Petri net, producer/consumer problem, Petri net language, formal language, regular language, finite automaton, regular expression, star-heightAbstract
We consider a Petri net for the producer/consumer problem (one of the classical synchronization problems) with the bounded buffer of size n and the regular formal languages Ln, generated by the net. We propose regular expressions denoting these languages in the recursive form, in case of the bounded buffer of size from 1 to 3 the explicit formulas are proposed. We transform a reachability graph into a finite automaton and use the state elimination method. We give an upper estimate for the star-height of the mentioned languages, in case of the bounded buffer of size 1 and 2 the exact values are calculated. We also consider union, intersection, Kleene closure, concatenation and set difference operations on mentioned languages. We give the finite automaton and propose regular expressions denoting the set difference of languages Ln \ L1 in the recursive form, for L2 \ L1 the explicit formula is proposed.References
J. Peterson, Petri net theory and modeling of systems. Moscow: Mir, 1984.
V.E. Kotov, Petri nets. Moscow: Nauka, 1984.
T. Murata, “Petri nets: Properties, analysis and applications”, Trudy Instituta inzhenerov po elektrotekhnike i radioelektronike, vol. 77, no. 4, pp. 41–85, 1989.
A.E. Pentus and M.R. Pentus, Formal language theory. Moscow: Mekhaniko-matematicheskii fakul’tet Moskovskogo Gosudarstvenogo Universiteta, 2004.
A.E. Pentus and M.R. Pentus, The mathematical theory of formal languages. Moscow: Binom, 2006.
S. Ginsburg, The mathematical theory of context-free languages. Moscow: Mir, 1970.
J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to automata theory, languages, and computation, 2nd ed. Moscow: Williams Publishing House, 2002.
V.M. Statkevych, “Regular expressions for producer/consumer Petri net languages with bounded buffer of size 1 and 2”, in 19th Int. Conf. on System Analysis and Information Technology (SAIT), Kyiv, Educational and Scientific Complex “Institute for Applied System Analysis” of National Technical University of Ukraine “Kyiv Polytechnic Institute”, 22–25 May 2017, pp. 123.
V. Statkevych, “On regular expressions for producer/consumer Petri net languages with bounded buffer”, in 4th Int. Scientific Conf. Nonlinear Analysis and Applications on memory of corresponding member of National Academy of Science of Ukraine V.S. Mel’nik, Kyiv, National Technical University of Ukraine “Kyiv Polytechnic Institute”, 4–6 Apr. 2018, pp. 68.
V. Mukhin and V. Statkevych, “On one context-free language for producer/consumer Petri net with the unbounded buffer”, in 15th Int. Conf. on Development and Application Systems (DAS), Suceava, Romania, 21–23 May 2020, pp. 137–140. doi: 10.1109/DAS49615.2020.9108948
M.Z. Zgurovsky and V.A. Denisenko, Discrete-continuous systems with controlled structure. Theory, modeling, applications. Kiev: Naukova Dumka, 1998.
A. Salomaa, Jewels of formal language theory. Moscow: Mir, 1986.
R. Valk and G. Vidal-Naquet, “Petri nets and regular languages”, Journal of Computer and System Sciences, vol. 23, issue 3, pp. 299–325, 1981.
A. Gronewold and H. Fleischhack, “Computing Petri net languages by reductions”, in 10th Int. Conf. Fundamentals of computation theory (FCT), Drezden, Germany, Springer, 22–25 Aug. 1995, pp. 253–262. doi: 10.1007/3-540-60249-6_57
S.V. Baumgertner and B.F. Melnikov, “Multi-heuristic approach for the star-height minimization of non-deterministic finite automata”, Proceedings of Voronezh State University. Series: Systems analysis and information technologies, no. 1, pp. 5–7, 2010.
