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

Применение отрицания к сильно связным автоматам

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

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

Аннотация: Вводится понятие результата применения к инициальному автомату функции $ f $, заданной на его выходном алфавите, как минимизированный инициальный автомат, реализующий определённую ограниченно-детерминированную функцию. Найдено достаточное условие его сильной связности. Также введено понятия остова - неинициального автомата без выходной функции - и результата применения функции к нему, как неинициальный аналог предыдущего определения. Рассмотрены результаты применения отрицания к остовам определённого вида. Для результата применения отрицания к сильно связному автомату с входным и выходным алфавитам $ \{0,1\} $ получены верхняя и нижняя оценки числа состояний, для чего было рассмотрено обобщение понятия пространства циклов на ориентированные графы.

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