EN
О числе состояний автомата, модифицирующего свою диаграмму
Опубликована: 2024 год, том 28, выпуск 1, С. 86–97
Аннотация
Вводятся понятия правила - пары слов одинаковой длины, и результата применения его к конечному инициальному автомату, когда в случае вывода первого слова из этой пары оно заменяется на диаграмме на второе. В работе исследуется результат применения правила к автомату, как словарная функция и как реализующий её конечный автомат. Показана эквивалентность двух определений результата применения правила к автомату. Показано, что он реализует ограниченно-детерминированную функцию. Получены оценки на наибольшее и наименьшее число состояний соответствующего ей приведённого конечного инициального автомата.
Ключевые слова: конечный инициальный автомат, самомодифицирующийся конечный автомат, диаграмма Мура.
BibTeX
@article{IS-Maslenikov2024,
author = {Маслеников, Денис Олегович},
title = {{О числе состояний автомата, модифицирующего свою диаграмму}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2024},
volume = {28},
number = {1},
pages = {86--97},
}
AMSBIB
\RBibitem{IS-Maslenikov2024}
\by Д.\,О.~Маслеников
\paper О числе состояний автомата, модифицирующего свою диаграмму
\jour Интеллектуальные системы. Теория и приложения
\yr 2024
\vol 28
\issue 1
\pages 86--97