Часть 3. Математические модели

О числе состояний автомата, модифицирующего свою диаграмму

Д. О. Маслеников

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Вводятся понятия правила - пары слов одинаковой длины, и результата применения его к конечному инициальному автомату, когда в случае вывода первого слова из этой пары оно заменяется на диаграмме на второе.
В работе исследуется результат применения правила к автомату, как словарная функция и как реализующий её конечный автомат. Показана эквивалентность двух определений результата применения правила к автомату. Показано, что он реализует ограниченно-детерминированную функцию. Получены оценки на наибольшее и наименьшее число состояний соответствующего ей приведённого конечного инициального автомата.

Ключевые слова: конечный инициальный автомат, самомодифицирующийся конечный автомат, диаграмма Мура