Software & Systems

Недетерминированным конечным автоматом (НКА) называется пятерка A=(Q, S, d, I, F), где Q – конечное множество состояний (вершин автомата); S – конечный алфавит; d:Q´S®2Q – функция переходов; I и F – соответственно множества начальных и конечных состояний. НКА называется детерминированным (ДКА) тогда и только тогда, когда ïIï=1 и "qÎQ, "aÎS:ïd(q, a)ï=1 (иногда ïd(q, a)ï£1).

Конечные автоматы (КА) широко применяются в разных областях, в частности в теории формальных языков, где они наряду с другими структурами, например регулярными выражениями (РВ), используются для описания языков [1].

В теории конечных автоматов одной из важнейших является задача вершинной минимизации, которая формулируется следующим образом: для данного автомата  найти эквивалентный ему автомат (то есть автомат, задающий тот же язык), который имел бы минимально возможное число состояний. Как показано в [2], для НКА задача вершинной минимизации является вычислительно трудной (PSPACE-полной), в то время как для ДКА соответствующая задача имеет сложность O(n×log(n)), где n – число состояний в автомате.

Из-за малой практической применимости алгоритмы вершинной минимизации НКА (особенно их точные версии) обычно не реализуются в большинстве программ для работы с конечными автоматами и родственными структурами. Рассмотрим некоторые возможности нового экспериментального программного средства ReFaM (Rational Expressions and Finite Automata Minimiza­tion). Основными отличиями данной программы от других программ для работы с КА являются реализация нескольких точных и приближенных алгоритмов минимизации НКА и возможность получения подробного отчета и статистики о каждом шаге работы алгоритма. Все это делает возможным применение рассматриваемой программы как в исследовательских, так и в учебных целях.

Основные сведения о программе ReFaM

Настоящая программа является проектом с открытым исходным кодом, написанным на языке C++. Данный проект – это часть библиотеки параллельных метаэвристических алгоритмов HeO [3]. Для описания КА в программе ReFaM используется xml-формат. Приведем пример xml-описа­ния НКА (на рисунке соответствующий автомат представлен в виде графа):

Каждому символу и состоянию в автомате присваивается уникальный номер (id). При описании автоматов узлы и , описывающие метки символов и состояний, могут быть опущены пользователем. В этом случае данные метки генерируются автоматически. В автоматах допускается наличие пустых e-переходов.

Список команд ReFaM с описанием их аргументов приведен в таблице 1.

Большинство команд ReFaM имеют вид command in_dir out_dir. Каждая такая команда сканирует все xml-файлы в каталоге in_dir и, если в них содержатся описания автомата или регулярного выражения, обрабатывает их содержимое, а результаты помещает в каталог out_dir. Назначение многих команд понятно из их названия. Остановимся подробнее на некоторых командах.

Команда canonize строит для данного автомата минимальный детерминированный (канонический) автомат. Команда re2fa формирует по данному регулярному выражению конечный автомат (с e-переходами), используя теорему Клини. Команда export позволяет конвертировать xml-представление автоматов в другие форматы. Команда generate может использоваться для случайной генерации автоматов. Как правило, подобные команды имеются и в других программах для работы с КА.

Команда export может использоваться для автоматического перевода xml-представления автоматов в иные форматы: GAP (для использования в пакете Automata программы GAP), Graph­viz (для построения графов автоматов в программе Graphviz), а также для получения таблиц переходов в текстовом формате и в формате LaTeX. Например, в результате экспорта xml-опи­сания НКА в формат GAP получается следующий результат:

Automaton("epsilon", 3, 4, [[,[2],], [[2],[2],[1,3]], [[2],,], [[3],,]], [1], [2,3]),

а описание таблицы переходов в формате LaTeX будет выглядеть так:

\documentclass[12pt]{article}

\usepackage[cp1251]{inputenc}

\usepackage{amssymb}

\begin{document}

Automaton example (symbols: 3, states: 3, transitions: 7, type: epsilon)

\begin{tabular}{lr||c|c|c|c}

 & & $a$ & $b$ & $c$ & $\epsilon$ \\

\hline

\hline

$ ightarrow$ & $1$ & $\varnothing$ & $\{2\}$ & $\{2\}$ & $\{3\}$ \\

\hline

$\leftarrow$ & $2$ & $\{2\}$ & $\{2\}$ & $\varnothing$ & $\varnothing$ \\

\hline

$\leftarrow$ & $3$ & $\varnothing$ & $\{1,3\}$ & $\varnothing$ & $\varnothing$ \\

\end{tabular}

\end{document}

С помощью команд build_ba и build_com могут быть построены соответственно базисный и полный (COM) автоматы для данного КА или РВ. Оба автомата являются инвариантами для данного регулярного языка, а их определение и алгоритмы построения можно найти, например, в [1]. Заметим, что в известных программах для работы с КА возможность построения данных автоматов отсутствует, кроме того, оба автомата могут использоваться для минимизации НКА по различным критериям.

Вершинная минимизация НКА осуществляется с помощью двух команд – min_kw и min_com. В настоящее время в программе ReFaM реализованы точные и приближенные алгоритмы минимизации, основанные на классическом алгоритме Камеды–Вейнера [4] и алгоритме, использующем COM-автомат [1, 5]. В обоих алгоритмах используются двоичные матрицы соответствия состояний (RAM и таблица # соответственно) и минимальные автоматы строятся на основе покрытий данных матриц гридами (подмножествами строк и столбцов). Второй метод идеологически ближе к методу минимизации на основе так называемого уиверсального автомата [6]. Кроме входного и выходного каталогов, в этих командах дополнительно могут указываться конфигурационный файл config.xml с настройками алгоритмов минимизации и начальное значение генератора случайных чисел seed для эвристических версий алгоритмов.

В числе отличительных особенностей ReFaM – распараллеливание наиболее трудоемких частей алгоритмов с использованием технологий параллельного программирования OpenMP и MPI и возможность получения подробного отчета и статистики о каждом шаге процесса минимизации. Например, для точного алгоритма Камеды–Вейнера в отчете показываются следующие объекты: исходный автомат A, автоматы det(A) – соответствующий ДКА, rev(A) – зеркальный автомат для A, det(rev(A)) – детерминированный зеркальный автомат для A, min(det(A)) – канонический автомат для A, min(det(rev(A))) – зеркальный канонический автомат для A, а также матрица RAM автомата A и гриды матрицы RAM.

Кроме того, для данного алгоритма собирается определенная статистика: размеры всех автоматов, число строк, столбцов, единиц и гридов в матрице RAM, плотность единиц в матрице RAM и др., а также замеряется время выполнения каждого шага алгоритма. В конце работы данные результаты статистически обрабатываются: вычисляются минимальные, максимальные и средние значения, а также среднеквадратическое отклонение. При этом имеется возможность задавать подробность отчета с помощью уровней от 0 (только статистика) до 3 (самый подробный отчет). Аналогичным образом документируется минимизация на основе COM-автомата.

Численные эксперименты

Как уже было отмечено, задача вершинной минимизации НКА является вычислительно трудной. Поскольку в точных алгоритмах вершинной минимизации используется полный перебор, то из-за сложности возникающих в процессе минимизации объектов (размеров канонических автоматов, количества гридов и т.п.) данный этап может оказаться очень длительным даже для сравнительно небольших автоматов. Очень интересной задачей является практическое изучение статистических свойств объектов, возникающих в процессе минимизации, в зависимости от характера входных данных. Для решения данной задачи может использоваться программа ReFaM.

В командах min_kw и min_com предусмотрена возможность, позволяющая с помощью соответствующей опции в конфигурационном файле построить все необходимые для минимизации объекты, не запуская сам процесс поиска.

Рассмотрим результат обработки трех случайных выборок из ста попарно независимых НКА без недостижимых и бесполезных состояний со следующими параметрами: число состояний ïQï=10, число начальных состояний ïIï=1, число конечных состояний ïFï=2, размер алфавита ïSï=2, плотность переходов 0,2; 0,3; 0,4, где T – число переходов в автомате (40, 60 и 80 соответственно).

Для каждой выборки оценивались число состояний в автоматах det(A) и det(rev(A)), число непустых состояний в канонических автоматах (число строк и столбцов RAM), размер, плотность единиц и число гридов в RAM. Результаты исследования представлены в таблице 2 (m – среднее значение, s – среднеквадратическое отклонение). Из приведенных данных видно, что для рассматриваемых выборок с увеличением плотности переходов средняя сложность рассматриваемых объектов уменьшается.

В заключение следует отметить, что в работе были рассмотрены некоторые возможности программы ReFaM, предназначенной для минимизации НКА. Отличительными особенностями программы являются возможность получения подробных отчетов о процессе минимизации и сбор обширной статистики, что делает возможным применение данной программы как в исследовательских, так и в учебных целях.

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

Литература

1.     Мельников Б.Ф. Недетерминированные конечные автоматы. Тольятти: Изд-во ТГУ, 2009. 160 с.

2.     Jiang T., Ravikumar B. Minimal NFA problems are hard. SIAM J. Comput. 1993. December. Vol. 22, pp. 1117–1141.

3.     Цыганов А.В., Булычов О.И. HeO: библиотека метаэвристик для задач дискретной оптимизации // Программные продукты и системы. 2009. № 4. С. 148–151.

4.     Kameda T., Weiner P. On the State Minimization of Nondeterministic Finite Automata. IEEE Transactions on Computers. 1970. Vol. 19, pp. 617–627.

5.     Melnikov B. A new algorithm of the state-minimization for the nondeterministic finite automata. Journal of Applied Mathematics and Computing. 1999. Vol. 6, pp. 277–290.

6.     Polak L. Minimalizations of NFA using the universal automaton // Int. J. Found. Comput. Sci. 2005. Vol. 16, no. 5, pp. 999–1010.