State Transition Table of a Finite Automata: a Science Project for High School Students
Abstract
Since the late 1960s, the problem of minimizing non-deterministic finite automata has been studied. In practical programs for large dimensions, obtaining an exact answer usually takes an unacceptably long time. In this regard, we are interested in, among others, heuristic algorithms for solving the problem, i.e. in algorithms that ``do not promise anything'', which, however, in practice in most cases, they give a solution that is close to optimal for an acceptable working time.
The project proposed for schoolchildren is aimed at a partial solution of one of the auxiliary tasks arising in the mentioned optimization problem. To do this, we define in a special way the equivalence relation on the set of tables of a given size M x N filled with elements 0 and 1. Obtaining the number of nonequivalent tables of dimension 8 x 10 will be a serious step on the way to proving the fact that the example of the ``bad'' automaton described in 1970 (the so-called Waterloo automaton) is the minimal possible example, not having ``lesser'' analogues.
To solve the problem, we first propose a bad algorithm, which consists in a simple enumeration of matrices. This algorithm works well on matrices of small dimensions, but, as usual in such situations, it works unacceptably long when moving to large dimensions. To reduce the operating time of the algorithm, we offer several heuristics, and present the results of the work of different versions of the program. The goal of the project is the creation of new heuristics, an even greater increase in the operating time of the program and, if possible, obtaining an answer (the number of tables) for the dimension 8 x 10.
For the majority of variants of the algorithm described in the paper, we present the implementation in C# using the principles of the object-oriented programming. We assume that further work on the project will consist in further modification of the programs we have provided.
References
Yu. Medvedev, A class of events that can be represented in a 1nite state machine. Automata, Moscow, USSR: Inostrannaya literatura, 1956, pp. 385–401 (in Russian).
Lectures by Turing Prize winners in their 1rst twenty years, Moscow, Russia: Mir, 1993 (in Russian).
A. V. Aho and J. D. Ullman, The Theory of Parsing, Translation, and Compiling, vol. 1, Moscow, USSR: Mir, 1978 (in Russian).
J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Moscow, Russia: Williams, 2002 (in Russian).
T. Jiang and B. Ravikumar “Minimal NFA problems are hard,” SIAM Journal on Computing, vol. 22, no. 6, pp. 117–1141, 1993; doi: doi.org/10.1137/0222067
L. Pol´ak, “Minimalizations of NFA using the universal automaton,” International Journal of Foundation of Computer Science, vol.16, no. 5, pp. 999–1010, 2005; doi: 10.1142/S0129054105003431
T. Kameda and P. Weiner, “On the state minimization of nondeterministic 1nite automata,” IEEE Transactions on Computers, vol. C-19, no. 7, pp. 617–627, 1970; doi: 10.1109/T-C.1970.222994
S. Lombardy and J. Sakarovitch, “The universal automaton. Logic and Automata,” Amsterdam University Press, pp. 457–504, 2008.
F. Harary, Graph Theory, Editorial URSS, Moscow, Russia, 2003 (in Russian).
F. Harary and E. M. Palmer, Graphical Enumeration, Moscow, USSR: Mir, 1977 (in Russian).
R. Gera , S. Hedetniemi , C. Larson, Eds. Graph Theory. Favorite Conjectures and Open Problems — 1, Basel, Switzerland: Springer, 2016.
R. Gera, T. Haynes, S. Hedetniemi, Eds. Graph Theory. Favorite Conjectures and Open Problems — 2, Basel, Switzerland: Springer, 2018.
V. N. Dolgov and B. F. Melnikov, “¸onstruction of universal 1nite automaton. I. From theory to the practical algorithm,” Proceedings of Voronezh State University. Series: Physics. Mathematics, no. 2, pp. 173–181, 2013 (in Russian).
V. N. Dolgov and B. F. Melnikov, “Construction of universal 1nite automaton. II. Examples of algorithms functioning,” Proceedings of Voronezh State University. Series: Physics. Mathematics. no. 1, pp. 78–85, 2014. (in Russian).
B. Melnikov, “The complete 1nite automaton,” International Journal of Open Information Technologies, vol. 5, no. 10, pp. 9–17, 2017.
B. Melnikov and E. Melnikova, “Waterloo-like 1nite automata and algorithms for their automatic construction,” International Journal of Open Information Technologies, vol. 5, no. 12, pp. 8–15, 2017.
A. V. Krivolapova, E. A. Melnikova, and N. V. Sofonova, “Some supporting algorithms of construction of waterloo-like automata,” Proceedings of Voronezh State University. Series: Systems analysis and information technologies, no. 4, pp. 20–28, 2016 (in Russian).
M. E. Abramyan, B. F. Melnikov, and M. A. Trenina, “Implementation of the Branch and Bound Method for the Problem of Recovering a Distances Matrix Between DNA Strings,” Modern Information Technologies and IT-Education, vol. 15, no. 1, 2019 (in Russian).
B. Melnikov, A. Nichiporchuk, M. Trenina, and M. Abramyan, “Clustering of situations in solving applied optimization problems (on the examples of traveling salesman problem and distance matrix recovery),” International Journal of Open Information Technologies, vol. 7, no. 5, pp. 1–8, 2019.
This work is licensed under a Creative Commons Attribution 4.0 International License.
