Известные алгоритмы перехода от DFA к регулярному выражению

Мне было интересно, существует ли «лучший» (я объясню в каком смысле) алгоритм для запуска из DFA и построения регулярного выражения такого что , чем в книге Хопкрофта и Уллмана (1979). Там наборы используются для представления наборов строк, которые переводят DFA из состояния в без прохождения через любое состояние, пронумерованное выше . Эта конструкция, хотя и очевидно правильная и очень полезная, является довольно технической. $\mathcal{A}$ $r$ $L(\mathcal{A})=L(r)$ $R_{ij}^k$ $q_i$ $q_j$ $k$

Я пишу монографию по теории алгебраических автоматов, и я не хочу отвлекать свою аудиторию слишком большим количеством технических деталей (по крайней мере, не деталями, которые не имеют отношения к результатам, которые я хочу показать), но я хочу включить доказательство эквивалентности между DFA и регулярными выражениями для полноты картины. Для записи я использую автоматы Глушкова для перехода от регулярного выражения к DFA. Это казалось более интуитивным, чем -transitions, которые я вообще не определял (опять же, потому что они мне не нужны). $\varepsilon$

Какие другие алгоритмы известны как переход от DFA к регулярному выражению? Я ценю простоту, а не эффективность (для меня это «лучше»), но это не является обязательным требованием.

Заранее спасибо за вашу помощь!

fl.formal-languages automata-theory regular-expressions Janoma
источник

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

R_{i j}^{k}

$R^k_{ij}$

k

$k$

Макс

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

R_{i j}^{k}

$R^k_{ij}$

Ян Йоханнсен

Я согласен. Это в основном алгоритм Флойда-Варшалла. Он также может быть получен с использованием стандартных методов динамического программирования (как это может сделать Флойд-Варшалл).

Дэвид

Я уверен, что отвечал на такой вопрос раньше, но я не могу его найти.

Рафаэль

@ Макс, не могли бы вы найти ссылку? Меня интересует матричное представление, оно должно быть более привлекательным для алгебры.

Janoma

Ответы:

Еще две конструкции: исключение состояний Бжозовского-МакКласки [1] и устранение Гаусса в системе уравнений с использованием леммы Ардена. Вероятно, лучшим источником является книга Жака Сакаровича [2].

[1] Дж. Бжозовский, Э. Маккласки-младший, Методы графа потока сигналов для последовательных диаграмм состояний цепей, транзакции IEEE на электронных компьютерах EC-12 (1963) 67–76.

[2] Дж. Сакарович, Элементы теории автоматов. Издательство Кембриджского университета, 2009.

Сильвен
источник

Я считаю, что подход к решению уравнений с использованием леммы Ардена является наиболее простым и легким для объяснения, поэтому я представляю его таким образом на начальном уроке теории.

Ян Йоханнсен

Метод системы уравнений звучит блестяще. К сожалению, в библиотеке моего университета нет книги, которую вы упоминаете (Сакарович), но я собираюсь поискать в другом месте.

Janoma

Сравнение конструкций также найдено в статье Сакаровича «Язык, выражение и (маленький) автомат», CIAA 2005, LNCS 3845, Springer (2006) 15-30. См. Infres.enst.fr/~jsaka/PUB/Files/LESA.pdf

Герман Грубер

Также обратите внимание, что порядок, в котором обрабатываются состояния, может сильно повлиять на размер получаемого регулярного выражения. Это всегда верно: делаете ли вы это с леммой Ардена, МакНотоном-Ямадой, устранением состояния или другим вариантом. Доступно несколько простых эвристик для выбора удачного заказа.

Герман Грубер

В книге Козена «Автоматы и вычислимость» упоминается элегантное обобщение этого алгоритма Флойда-Варшалла. Поскольку вы упомянули обращение к алгебраистам, вы можете найти это полезным. Вы найдете это на странице 58-59 этого текста. (Я думаю, что у книг Google есть предварительный просмотр.)

$2 \times 2$

$\begin{bmatrix} a & b \\ c & d \end{bmatrix}^* = \begin{bmatrix} (a+bd^*c)^* & (a+bd^*c)^*bd^* \\ (d+ca^*b)^*ca^* & (d+ca^*b)^* \end{bmatrix}$

$i,j$ $i$ $j$

$n \times n$ $a,b,c,d$ $m\times m$ $m\times (n-m)$ $(n-m) \times m$ $(n-m) \times (n-m)$ $2 \times 2$ $2 \times 2$

$n$ $T$ $\sum_{f \in F} (T^*)_{s,f}$ $s$ $T^*$

$m=1$ $R_{ij}^k$

Другой вывод структур алгебры Клини над матрицами приведен в «Теореме полноты для алгебр Клини и алгебры регулярных событий » Козена.

mikero
источник

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

Я написал этот документ, объясняющий метод для студентов прошлым летом. Это напрямую связано с конкретной лекцией; упомянутая ссылка является типичным определением регулярных выражений. Доказательство леммы Ардена содержится; один для правильности метода отсутствует. Как я узнал об этом в лекции, к сожалению, у меня нет ссылки.

Рафаэль
источник

Я также предпочитаю это доказательство. Я нахожу это элегантным и легко объяснить. Даже лемма Ардена не сложна. Я думаю, что это будет метод, который я включу в свой документ.

Janoma

+

$+$

\cup

$\cup$

\cup

$\cup$