Авторы: Н.В. Ногина, И.С. Грунский
Источник: Публикация [Перейти]
УДК 519.713
Институт информатики и искусственного интеллекта
ГВУЗ «Донецкий национальный технический университет»
Украина, 83050, г. Донецк, пр. Б. Хмельницкого, 84
Синтез регулярного выражения языка, порожденного помеченным графом,
методом его локальной редукции
N.V. Nogina, I.S. Grunsky
Institute of Informatics and Artificial Intelligence of Donetsk National Technical University Ukraine, 83050, c. Donetsk, B. Khmelnitsky ave., 84
Synthesis of Regular Expression for Language Generated by a Labeled Graph by Means of its Local Reduction
Н.В. Ногіна, І.С. Грунський
Інститут інформатики і штучного інтелекту ДВНЗ «Донецький національний технічний університет» Україна, 83050, м. Донецьк, пр. Б. Хмельницького, 84
Синтез регулярного виразу мови, що породжена поміченим графом, методом його локальної редукції
Предлагается новый алгоритм анализа языков, порожденных графами с помеченными вершинами и дугами. Он позволяет находить алгебраическое выражение (в терминах соответствующей алгебры) таких языков. Алгоритм основан на локальной редукции графа, т.е. на последовательном исключении его вершин и дуг. Предложен порядок редукции, при котором исключение вершин проводится от финальной к начальной, а также упрощение графа в процессе редукции, что зачастую позволяет уменьшить объем вычислений.
Ключевые слова: помеченный граф, алгебра языка, регулярное выражение, локальная редукция графа.
New algorithm for analysis of languages generated by graphs with labeled vertices and transitions is proposed. It gives regular expression (in terms of the proper algebra) describing the language. The algorithm is based on a local reduction of the graph, that is the sequential exclusion of vertices and transitions. It is proposed a reduction procedure, in which removal starting at the final vertex to initial, and a simplification of the graph in the process of reduction, which often reduces the amount of computations.
Key Words: labeled graphs, algebra of language, regular expression, local reduction of the graph.
Запропоновано новий алгоритм аналізу мов, породжених графами з поміченими вершинами і дугами. Він дозволяє знаходити алгебраїчний вираз (в термінах відповідної алгебри) таких мов. Алгоритм засновано на локальній редукції графа, тобто на послідовному виключенні його вершин та дуг. Запропоновано порядок редукції, при якому видалення вершин проводиться від фінальної до початкової, а також спрощення графа в процесі редукції, що часто дозволяє зменшити обсяг обчислень.
Ключові слова: помічений граф, алгебра мови, регулярний вираз, локальна редукція графа.
В настоящее время актуальны задачи, связанные с анализом и синтезом языков, представимых в помеченных графах. Интерес к изучению таких графов вызван тем, что существует ряд важных задач, которые естественным образом представляются в виде помеченных графов. Такие графы интенсивно изучаются при верификации программ и планировании движения мобильного робота [2].
Свойства языков, представимых графами с отмеченными дугами, изучались С. Клини. Им предложена широкоизвестная алгебра, описывающая эти языки. В настоящее время известен ряд алгоритмов описания этих языков в алгебре Клини и построение графов по такому описанию [3]. Свойства языков, представимых графами с отмеченными вершинами, рассматривались в работах [4,5,6,7]. В них предложены алгебры, аналогичные алгебре Клини, для описания языков, порожденных такими графами, и алгоритмы перехода от алгебраических выражений, описывающих языки, к представляющим их графам и наоборот.
В данной работе рассматривается алгебра, описывающая языки, порожденные графами с помеченными вершинами и дугами, частным случаем которой является алгебра, описанная в [4,5,6,7]. Рассматривается задача построения алгебраического выражения языков, представимых в таких графах.
Целью данной работы является разработка нового алгоритма построения регулярного выражения по заданному помеченному графу.
Основные определения и обозначения
Помеченным графом назовем восьмерку , где – конечное множество вершин, – множество дуг, – множество отметок вершин, – множество отметок дуг, – функция разметки вершин, – функция разметки дуг, – начальная вершина графа, – множество финальных вершин. вершины в финальную. Языком , порождаемым графом , назовем множество отметок всех успешных путей.
Пусть Pre(qi) – множество начальных вершин всех дуг, входящих в qi, Post(qi) – множество конечных вершин всех дуг, исходящих из qi.
Преходящей вершиной назовем вершину q ≠ q0 , у которой Pre(q) = Æ, а висячей – q ≠ fin, у которой Post(q) = Æ.
Пусть – множество всех непустых слов вида . Рассмотрим алгебру ,⊛,, в которой операции на языках L1, L2, L Í Z+ определены следующим образом:
1) операция объединения: = ;
2) операция сочленения (склеивания) слов: ;
3) операция итерации (зацикливания): L⊛ = , где L0= LначLкон, причем Lнач={x| xw=L, x=X}, Lкон= {x| w’=L, x =X}; L1=L; Ln+1=Ln◦L для всеx n≥1 .
Регулярные выражения определим индуктивно:
1) пустое множество Æ является регулярным выражением;
2) x, xyx’ являются регулярными выражениями для всех символов x,x’=X, y = Y;
3) если p и q – регулярные выражения, то выражения p◦q, pq, p⊛ также являются регулярными.
Постановка задачи
В данной работе решается следующая задача. Дан конечный ориентированный связный помеченный граф. Требуется разработать алгоритм построения регулярного выражения языка, порождаемого этим графом.
Решение систем линейных уравнений
Очевидно, что по аналогии с работой [5] для любого помеченного графа G, порождающего язык L(G), можно найти регулярное выражение R, для которого L(R)=L(G).
Для решения системы линейных уравнений (1) можно использовать метод многократного удаления неизвестных, подобный классическому методу Гаусса. Используя (2), можно удалить Ln из правой части последнего уравнения в системе (1). Полученное значение для Ln можно подставить в предпоследнее уравнение и получить выражение для Ln-1, которое зависит только от L1…Ln-2. Продолжая такие подстановки для всех оставшихся в системе уравнений, можно получить значения всех Li, которые будут регулярными выражениями в рассматриваемой алгебре.
Алгоритм построения регулярного выражения
Вход. Граф G с отмеченными вершинами, с начальной и финальными вершинами.
Выход. Регулярное выражение языка, порожденного исходным графом.
Шаг 1. Граф G превращается в граф с отмеченными дугами. Для этого отметки вершин стираются и в дугах (qi, ei, qj) отметкой ei становится xiyixj, где xk=m(qk), где k=i,j, yi=ρ(ei).
В список вершин вводится фиктивная конечная вершина fin, а в список дуг – дуга из каждой финальной вершины qi в вершину fin с отметкой вершины qi.
Шаг 2. Удаление преходящих и висячих вершин.
While в графе существует вершина q ≠ q0, у которой Pre(qi)=Æ do
Удаляем вершину qi и все дуги, исходящие из нее;
While в графе существует вершина qi≠ fin, у которой Post(qi) = Æ do
Удаляем вершину qi и все дуги, входящие в нее;
Шаг 3. If в графе существует хоть одна петля или существуют вершины, не являющиеся начальными, из которых исходит хоть одна дуга, then goto Шаг 4
else goto Шаг 7;
Шаг 4. Удаление кратных дуг и петель.
1. Удаляем кратные дуги, заменяя их одной дугой с отметкой, равной объединению отметок исходных дуг.
2. Удаляем все петли по следующему правилу.
Пусть в вершине qi есть петля с отметкой А. Если из этой вершины нет дуги в другую вершину, то петля удаляется. В противном случае для всех дуг (qi, ei, qj), где i≠j, с отметкой дуги В, петля удаляется, а отметка В заменяется отметкой А⊛, В ○ В.
На шагах 5 – 6 происходит удаление одной вершины.
Шаг 5.
Выбираем qi = Pre(fin);
q := qi;
Шаг 6.
If q ¹ q0 then удаляем вершину q и все входящие и выходящие из нее дуги. Если при этом есть произвольный путь из некоторой вершины qi в вершину qk, через удаляемую вершину q, где qj принадлежит Pre(q) и qk принадлежит Post(q), то в граф добавляется дуга, содержащая пометку, равную склеиванию пометок удаляемых дуг данного пути;
goto Шаг 2;
else qi равная q0 не исключается;
выбираем qm =Pre(q0);
q := qm;
goto Шаг 6;
Шаг 7. Удаляем все вершины q != q0 и q != fin и все входящие в них дуги. Получим граф, состоящий из двух вершин: q0 и fin и дуги, между ними с пометкой R, где R – это искомое регулярное выражение.
Анализ алгоритма
Из описания алгоритма следует, что алгоритм имеет следующую структуру: шаги 2 – 6 образуют внешний цикл алгоритма, шаги 5 – 6 образуют вложенный цикл алгоритма. При прохождении один раз внешнего цикла в графе удаляется по крайней мере одна вершина. Следовательно, внешний цикл выполняется O(n) раз, где n – число вершин помеченного графа. Таким образом, алгоритм завершает свою работу через конечное число шагов. При выполнении одного прохода по внешнему циклу на шаге 4 в графе удаляются кратные дуги и петли. Таким образом, перед началом выполнения шага 5 в графе может быть не более O(n2) дуг. При выполнении шагов 5 – 6 алгоритма удаляется одна вершина графа, при этом в графе удаляется не более O(n) дуг, и может быть добавлено не более O((n-1)2) новых дуг.
Из проведенных рассуждений следует, что если анализ одной дуги графа проводится в единицу времени, то алгоритм требует не более O(nm) единиц времени, где m – количество дуг в исходном графе.
Докажем правильность получаемого решения, показав, что все операции на графах, применяемые в данном алгоритме, фактически соответствуют методу решения систем линейных уравнений рассматриваемой алгебры.
1. Операция удаления вершины соответствует подстановке одного уравнения в другое:
2. Операция удаления кратных ребер обоснована дистрибутивным законом рассматриваемой алгебры:
.
3. Операция удаления петли соответствует решению (2) линейного уравнения с одним неизвестным данной алгебры.
4. Удаление висячих вершин на Шаге 2 обосновано тем, что язык, порождаемый такой вершиной, пуст, поскольку из этих вершин вершина fin недостижима.
5. Очевидно, что удаление преходящих вершин и всех исходящих из них дуг на Шаге 2 возможно без изменения множества успешных путей в помеченном графе, поскольку данные вершины недостижимы из начальной.
Таким образом, все операции на графах, выполняемые предложенным алгоритмом, соответствуют методу решения системы линейных уравнений в данной алгебре. Следовательно, алгоритм корректен.
Алгоритм основан на локальной редукции графа, т.е. на последовательном исключении его вершин и дуг. Предложен порядок редукции, при котором исключение вершин проводится от финальной к начальной. Такой порядок позволяет не обрабатывать вершины, из которых fin не достижима, и они удаляются все сразу на шаге 7.
В алгоритме предусмотрено упрощение графа. Оно достигается, во-первых, путем последовательного удаления всех преходящих и висячих вершин (шаг 2) и, во-вторых, путем удаления всех петель и кратных дуг (шаг 3) перед каждым удалением вершины (шаг 5 – 6). Таким образом, это упрощение, по сути, является построением аналога трима [8, с. 23]. Порядок исключения вершин и приемы упрощения графа являются, на наш взгляд, весомыми достоинствами предложенного алгоритма.
Предложенный алгоритм позволяет находить регулярное выражение языка, порожденного графом с помеченными вершинами и дугами.
В отличие от алгоритмов решения этой задачи, основанных на решении системы линейных уравнений в данном алгоритме учитывается структура графа, что зачастую позволяет уменьшить объем вычислений.
Literatura