Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции

Abstract

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