Алгоритмы преобразования конечных автоматов, соответствующих бесконечным итерационным деревьям
Authors: Абрамян М.Э. , Мельников Б.Ф. 
Published: December 2024

В настоящей статье мы работаем с несколькими различными вариантами конечных автоматов, каждый из которых соответствует бесконечному итерационному дереву, построенному для некоторого заданного морфизма. При этом каждый из построенных для некоторого морфизма автоматов описывает основные свойства этого морфизма. Кроме того, в каждом случае (т. е. для каждого варианта автомата) возникает также следующая «обратная задача»: необходимо описать морфизм (либо просто указать пару языков), для которого получается такой заданный автомат. Мы приводим компьютерную программу построения одного из таких автоматов – т. н. автомата PRI. После этого мы рассматриваем подробный пример автомата PRI для пары несовпадающих языков. Продолжая рассматривать этот пример, мы с последним автоматом выполняем обычные преобразования, описанные и неоднократно применённые в наших предыдущих публикациях, а именно – детерминизацию и канонизацию зеркального автомата для возможного применения полученных результатов в алгоритме минимизации недетерминированных автоматов. В рассматриваемой нами ситуации таким минимальным автоматом является другой строимый на основе заданного дерева морфизма автомат – недетерминированный, т. н. автомат NSPRI# – и равенство этих автоматов (что влечёт эквивалентность PRI и NSPRI#) мы также показываем в статье на примере. На основе автомата NSPRI# с помощью тривиального (но неэквивалентного) преобразования строится недетерминированный автомат NSPRI – подробное исследование которого предполагается в дальнейших публикациях. Интерес представляют также примеры автоматов PRI и NSPRI# для пар совпадающих языков – мы также приводим один такой пример в настоящей статье.

In this paper, we work with some different variants of finite automata, each of which corresponds to an infinite iterative tree constructed for some given morphism. At the same time, each of the automata constructed for a given morphism describes the main properties of this morphism. Besides, in each case (i.e., for each variant of the automaton), the following “inverse problem” also arises: to describe the morphism (or simply specify a pair of languages) for which such a given automaton is obtained. We present a computer program for constructing one such automaton, so-called PRI automaton. After that, we consider a detailed example of a PRI automaton for a pair of different languages. Continuing to consider this example, we use the last automaton to perform usual transformations described and repeatedly applied in our previous publications, i.e., the determination and canonization of the mirror automaton for possible application of the results obtained in the algorithm for minimizing nondeterministic automata. In the considered situation, such a minimal automaton is another automaton constructed on the basis of a given morphism tree, a nondeterministic automaton, the so-called NSPRI# automaton, and we also show the equality of these automata (which implies the equivalence of PRI and NSPRI#) in the paper by an example. Based on the NSPRI# automaton, a non-deterministic NSPRI automaton is constructed using a trivial (but non-equivalent) transformation; a detailed study of this automaton is expected in future publications. Examples of PRI and NSPRI# automata for pairs of matching languages are also of interest, we also give one such example in this paper.