A Program Study of the Union of Semilattices on a Set of Subsets of Grids of the Waterloo Language - Mikhail Abramyan; Boris Melnikov (Современные информационные технологии и IT-образование)
Relevance. The relevance of the subject area under consideration is due to the need to study the set of regular languages, in particular to describe their various sub-classes. Also relevant are the tasks that may arise in some such subclasses. This will give, among other things, the possibility of describing some new algorithms for equivalent transformation of nondeterministic finite automata. Purpose of the study. The aim is to study the set of subsets of grids of the Waterloo language from the point of view of abstract algebra. Materials and methods. The study was conducted using the library for working with nondeterministic finite automata NFALib implemented by one of the authors in C#, as well as statistical methods for analyzing algorithms. Results. The results are regularities obtained when considering semilattices on a set of subsets of grids of the Waterloo language. Conclusions. It follows from the results obtained that the minimum covering automaton equivalent to the Waterloo automaton can be obtained by adding one additional to the minimum covering set of grids. The calculations also show that in addition to the minimum covering automaton, it is possible to obtain 4 more minimum covering automata equivalent to the original Waterloo automaton, however, to obtain each of them, it is necessary to replace 1 or 2 grids included in the minimum covering set.