Рисунок 1 – Расширение xy-дуги, возможные подграфы
Авторы:Stefan Gulan
Источник:Публикация http://drops.dagstuhl.de/opus/volltexte/2011/3038/pdf/46.pdf
Перевод: Кондратюк Т.А.
При рассмотрении преобразования конечных автоматов в регулярных выражения, следует учитывать экспоненциальное увеличение регулярного выражения в зависимости от размеров автомата. Это связано со структурными свойствами графов, которые не могут непосредственно кодироваться регулярными выражениями. Чтобы идентифицировать эти структуры, мы обобщаем класс последовательно-параллельных диграфов для ациклических случаев. Полученные орграфы обратимо кодируются в регулярные выражения линейных размеров.
Основной результат теории регулярных языков эквивалентен описательной силе регулярных выражений и конечных автоматов, первоначально описанных Клини [9]. Обычные выражения понятны и естественны для человека; они выступают как средство, обозначающее такие языки. Автоматы же в свою очередь, используются для работы на машинном уровне. Следовательно, преобразование между двумя этими представлениями имеет большое практическое значение. Есть несколько линейных алгоритмов преобразования регулярных выражений в автоматы с линейным размером, подробный обзор данной тематики описан Уотсоном[16]. Мы остановимся на обратной стороне данного вопроса, который требует более детального рассмотрения и анализа.
В частности, Ehrenfeucht & Zeiger [3]предлагают класс автоматов, для которых размер либо эквивалент выражения являются экспоненциальными. Эти автоматы определены алфавитом, который растет в зависимости от размера автомата. Таким образом, Ellul и др. задались вопросом: "Существует ли подобное увеличение размера регулярного выражения, построенного по автомату с фиксированным алфавитом[4]". Утвердительный ответ на этот вопрос дали Gruber & Holzer [5], конкретно для бинарных алфавитов. В большинстве своем, исключается размер алфавита, как фактор, способствующий экспоненциальному увеличению регулярного выражения. Утверждается, что "автоматы с одноместным алфавитом могут быть преобразованы в выражения квадратничного размера с помощью нормальной формы Chrobak[1, 4].
Отметим, что конечный автомат - это орграф с помеченными дугами. Он имеет язык, который состоит из всех последовательностей меток, которые были найдены путем прохода от начального состояния в финальное. Происходит увеличение регулярных выражений и конечных автоматов, как комбинаторных объектов. Выражения являются условиями , т.е. линейными объектами, которые должны прибегать к повторным субтермам для того, чтобы передать информацию, закодированную в граф-структуре автомата. Ранее это отмечалось McNaughton [11], который утверждает: "Хотя каждое регулярное выражение может быть преобразовано в граф, который имеет ту же структуру, обратное преобразование будет не верным". Данная работа направлена на выявление графов, которые не могут преобразовывазться в выражения, имеющие ту же структуру.
Для автоматов, в основе которых лежат графы с параллельными дугами, Moreira & Reis [12] предложили метод эффективного преобразования регулярных выражений линейного размера. Эти графы характеризуются отсутствием ациклических подграфов, как это было показано в работе Valdes и др. [15]. Korenblit & Levit [10] предположили, что этот вид подграфа уже вызывает квадратичное увеличение размера выражений, построенных по ациклическому автомату.
Тем не менее, метод Moreira & Reis’s сводится к автоматам, которые принимают только конечные языки. Для того, чтобы принять бесконечный язык, автомат должен содержать циклы, которые относятся к классу последовательно-параллельных диграфов. Также было предложено искать различные виды подграфов[6], использовать эвристические методы для преобразования графов в регулярные выражения, т.к. на сегодняшний день не существует строгого теоретического анализа графов.
Все вышесказанное укрепляет наше обобщение последовательно-параллельных диграфов к ациклическим случаям. В п. 4 мы показываем, что такие графы могут быть преобразованы в регулярные выражения, и что каждое регулярное выражение кодирует граф этого класса.
Кодирование и декодирование производятся в рамках теории автоматов и могут быть применены в преобразовании между автоматами и выраженими. В П. 5 мы выводим характеристику нашего нового класса. Это означает, что автоматы имеют структуру графа, не могут быть закодированы с помощью регулярных выражений, и тем самым вызвать увеличение размера регулярного выражения, наблюдаемое в построении регулярные выражения по конечному автомату.
Мы считаем, что конечный автомат - это ориентированный граф с петлями и кратными дугами. Такие графы называются ориентированными псевдографами, но в дальнейшем мы будем называть их графами. Формально, граф это множество (V, A, t, h) с вершинами V, дугами A, конечной вершиной t: A->V, начальной вершиной h: A->V. Если граф Gне задан явно, пусть G=(VG, AG, tG, hG). Xy-дуга графа G это любая a∈AG с tG(a) =x и hG(a)=y; запишем это как a=xy∈AG. Xy-дуга a исходящее из x и входящее в y, x и y назовем конечной точкой для a. Отдельные xy-дуги графа параллельны друг другу. Xx-дуга - это x-цикл или просто цикл, каждая другая дуга - это правильная дуга. Степень входов x ∈ VG, обозначается d¯G(x), это количество дуг, входящих в x в графе G, степень выходов d+G(x) - это количество дуг, выходящих из x. Сокращение графа G - это любое правильная xy-дуга, где d+G(x) = 1 = d¯G(y). Вершина x ∈ VG является простой, если d¯G(x)≤1 и d+G(x)≤1.
Запишем F⊆G как F подграф G. Если F и G являются подграфами H и a=xy∈AH с x∈VF и y∈VG, тогда a назовем (F,G)-дугой, как и (x,G) - или (F,y) - дугой H. Путь длиной n, обозначим Pn, это граф, где n+1 вершин и n cокращений.
Подразделение дуги a = xy это замена a с xy-path длиной 2. В основном, подразделение графа G называют DG, как любой граф H, существуют графы G1,...,Gn, где G = G1,Gi+1 результатом подразделения которых является дуга Gi и Gn = H. Разделение вершины x - это замена x двумя вершинами x1 иx2, а также дугой x1x2. Эта дуга перенаправлена во все дуги, входящие в x и в x1. Перенаправление всех дуг выходящих из x, выходят из x2. Две вершины x,y∈VG соединены, т.е. заменены новой вершиной z и в данном случае перенаправлены те дуги, выходящие из x или y, и входящие или выходящие из z.
Граф G - дву-терминальный, если существует s, t∈VG, каждая x ∈VG лежит на некотором st- пути в графе G. Вершины s и t будут называться истоком и стоком графа G; запишем граф G = (G, s, t) и представим, что G - дву- терминальный граф с истоком s и стоком t. Дву-терминальный граф G = (G, s, t) назовем "гамаком". Пусть x и y будут вершинами графа (G, s, t): x преобладает над y, если x лежит на каждом sy-пути, и x со-доминирует y, если x лежит на каждом yt-пути. К тому же, x является щитом y, если x доминирует и со-доминирует y; также, x является щитом ребра a, если x является щитом обеих t(a) и h(a).
Рисунок 1 – Расширение xy-дуги, возможные подграфы
Рисунок 2 – Построение spl-графа из графа P1
[1] Marek Chrobak. Finite automat and unary languages. Theoretical Computer Science,(47):149–158, 1986.
[2] Reinhard Diestel. Graph Theory. Number 173 in Graduate Texts in Mathematics. Springer, 4 edition, 2010.
[3] A. Ehrenfeucht and P. Zeiger. Complexity measures for regular expressions. Journal of Computer and System Sciences, 12:134–146, 1976.
[4] K. Ellul, B. Krawetz, J. Shallit, and M.-W. Wang. Regular expressions: new results and open problems. Journal of Automata, Languages and Combinatorics, 10(4):407–437, 2005.
[5] H. Gruber and M. Holzer. Finite automat, digraph connectivity, and regular expression size. In ICALP 2008, Part II, volume 5126 of LNCS, pages 39–50, 2008.
[6] S. Gulan and H. Fernau. Local elimination-strategies in finite automata for shorter regular expressions. In SOFSEM 2008, volume 2, pages 46–57, 2008.
[7] S. Gulan and H. Fernau. An optimal construction of finite automata from regular expressions. In R. Hariharan et al., editor, 28th FSTTCS, pages 211–222, 2008.
[8] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
[9] S. C. Kleene. Representation of Events in Nerve Nets and Finite Automata, pages 3–41. Annals of Mathematics Studies. 1956.
[10] M. Korenblit and V. E. Levit. On algebraic expressions of series-parallel and fibonacci graphs. In C. S. Calude et al., editor, DMTCS 2003, number 2731 in LNCS, pages 215–224, 2003.
[11] R. McNaughton. Techniques for manipulating regular expressions. In J. F. Hart and S. Takasu, editors, Systems and Computer Science, pages 27–41. University of Toronto Press in association with the University of Western Ontario Toronto, 1967.
[12] Nelma Moreira and Rogerio Reis. Series-parallel automata and short regular expressions. Fundamenta Informaticae, 91(3-4):611–629, 2009.
[13] M.H.A. Newman. On theories with a combinatorial definition of ”equivalence”. Annals of Mathematics, 43(2), 1942.
[14] Enno Ohlebusch. Advanced Topics in Term Rewriting. Springer, 2002.
[15] Jacobo Valdes, Robert E. Tarjan, and Eugene L. Lawler. The recognition of series parallel digraphs. SIAM Journal on Computing, 11(2):298–313, 1981.
[16] B. W. Watson. A taxonomy of finite automata construction algorithms. Tech
Перевод: Кондратюк Т.А.