Минимизация – одна из самых важных задач теории конечных автоматов. Хотя её решение было описано достаточно давно, она не потеряла своей актуальности и в современных условиях. Под минимизацией конечного автомата понимают нахождение эквивалентного конечного автомата, минимального по какому-либо критерию. Эквивалентность автоматов означает то, что эти автоматы задают один и тот же язык (множество слов, принимаемых – распознаваемых – конечным автоматом). При минимизации эквивалентность является фундаментальным условием, так как нам необходимо, чтобы минимальный автомат задавал тот же язык, что и исходный. Иначе, просто теряется смысл такой минимизации.

Неравенство покрывающих автоматов заданному

В данной работе мы будем рассматривать минимальные автоматы, построенные на основе покрывающих. Под покрывающим автоматом мы здесь понимаем автомат, построенный на покрывающем подмножестве множества блоков таблицы бинарного отношения # (мы не будем останавливаться на этих объектах, все они подробно описаны в [1]).

В процессе построения минимального автомата мы определённым образом (индивидуально для каждого типа минимизации) выбираем блоки из таблицы бинарного отношения #, чтобы получилось покрывающее множество. И, на первый взгляд, этого должно быть достаточно для построения автомата, обеспечивающего минимум по одному из критериев. Однако покрывающий автомат в некоторых случаях может оказаться неэквивалентным исходному. Такая проблема характерна, например, для т.н. автомата Waterloo [2] и некоторых других, не столь известных [3]. И она требует от нас проводить дополнительные проверки в алгоритмах минимизации (прежде всего – в эвристических алгоритмах) – например, на соответствие циклов строимого автомата циклам базисного автомата.

В алгоритмах минимизации автомата предугадать наличие у данного автомата описанной проблемы – далеко не тривиальная задача: например, при построении практических алгоритмов возникает естественное предположение, что эта проблема присутствует для автоматов, приведённых далее в таблице 1, – поскольку минимальное покрывающее множество состоит всего из 2 блоков, которые, по первому предположению, не смогут обеспечить существование всех соответствующих циклов базисного автомата. Однако, это предположение неверно.

Таблица 1 – Таблица отношения # и блоки для неё.

Подход к моделированию

При помощи специального программного обеспечения, созданного в рамках работы над [4], было сгенерировано множество автоматов с различными характеристиками, для которых проводилась проверка на наличие описанной выше проблемы с использованием комплекса программ, разработанного автором специально для исследования рассматриваемой проблемы. Ниже приведены характеристики, которые варьировались[1] в генерируемых случайных автоматах.

1. Количество вершин;
2. Количество петель;
3. Вложенность петель;
4. Максимальное количество дуг, выходящих из вершины;
5. Максимальное количество дуг, входящих в вершину;
6. Минимальная длина пути от стартовой вершины до финальной, поделённая на количество вершин.

Но пока при практическом программировании не было обнаружено ни одного автомата, для которого покрывающий автомат был бы неэквивалентен исходному – однако в связи с естественными ограничениями на размерность задачи число состояний канонического автомата для рассматриваемого языка не превышало 25.

Список литературы

1. Мельников Б.Ф. Недетерминированные конечные автоматы. – Тольятти: Изд-во ТГУ, 2009. – 160 с.
2. Kameda T., Weiner P. On the state minimization of nondeterministic finite automata. – IEEE Trans. Computers. – 1970. – 19(7). – P. 617–627.
3. Polák L. Minimalizations of NFA using the universal automaton. – Int. J. Found. Comput. Sci. – 2005. 16(5). – P. 999-1010.
4. Рогова О.А. Подход к оценке репрезентативности случайно сгенерированных дискретных структур на примере недетерминированных конечных автоматов: дис. … канд. физ.-мат. наук: 05.13.18,  Тольяттинский государственный университет, Д212.264.03, защищена 13.04.2012 / О.А. Рогова – Тольятти: ТГУ, 2012. – 115 с.

Все статьи автора «Зубова Мария»