Использование алгебры регулярных событий

Внешнее поведение автомата может быть формализовано в виде системы регулярных выражений { R j}. Каждое R j задает множество всевозможных слов или событий во входном алфавите X, определяющее одну из реакций y i У искомого алфавита. Используемая для этих целей алгебра регулярных событий, введенная С.Клини, определяет лишь три операции: V – объединение, • – умножение, { }* – итерация слов или букв входного алфавита X.

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

Во избежание ложных путей (слов) на графе регулярного выражения вводятся пустые (без букв х Х) стрелки. Отметим наиболее характерные ситуации для введения пустых стрелок: 1) переход от одной итерации к последующей итерации; 2) открытие итерационных скобок; 3) закрытие итерационных скобок в дизъюнктивных членах (термах) регулярного выражения.

Кроме того пустые стрелки вводятся при построении автоматов многократного действия путем замыкания финитных вершин (отмеченных выходными сигналами у _j) на начальную вершину.

Далее осуществляется дедуктивный вывод абстрактного автомата, обеспечивающий выявление всех его внутренних состояний. За основу предлагается взять алгоритм Мелихова Ю.Н., предписывающий выполнение, следующих действий. Первоначально все графы регулярных выражений объединяются одной начальной вершиной по принципу макси­мального объединения стрелок. Этой вершине соответствует первый столбец последовательно заполняемой таблицы перехода искомого автомата.

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

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

И так до тех пор, пока содержимое всех клеток таблицы не будет совпадать с заголовками полученных столбцов. Последние ­ не что иное, как состояния искомого автомата Мура.

Завершающий шаг — построение отмеченной таблицы переходов. Для этого дизъюнкциям индексов каждого заголовка столбца (состояния автомата) приписываются дизъюнкции соответствующих выходных сигналов.

Дизъюнкции противоречивых (различных) выходных сигналов указывают на некорректность исходного графа. В этом случае описанную процедуру следует повторить, обратив особое внимание на получение корректного графа регулярного выражения.

Полученный автомат легко перестроить в эквивалентный ему автомат Мили, в результате чего может появиться дополнительная воз­можность минимизации числа состояний. Для этой цели необходимо воспользоваться известными из литературы алгоритмами минимизации, основанными на фундаментальных понятиях эквивалентности (совместимости) полностью (частично) определенных абстрактных автоматов.