Алгоритмы преобразования конечных автоматов, соответствующих бесконечным итерационным деревьям

Аннотация

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

Сведения об авторах

Mikhail Eduardovich Abramyan, Южный федеральный университет

доцент Института математики, механики и компьютерных наук им. И.И. Воровича, кандидат физико-математических наук, доцент

Boris Feliksovich Melnikov, Совместный университет МГУ-ППИ в Шэньчжэне

профессор факультета вычислительной математики и кибернетики, доктор физико-математических наук, профессор

Опубликована
2021-04-15
Как цитировать
ABRAMYAN, Mikhail Eduardovich; MELNIKOV, Boris Feliksovich. Алгоритмы преобразования конечных автоматов, соответствующих бесконечным итерационным деревьям. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 17, n. 1, apr. 2021. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/728>. Дата доступа: 22 oct. 2021 doi: https://doi.org/10.25559/SITITO.17.202101.728.
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук