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

28

Мне было интересно, существует ли «лучший» (я объясню в каком смысле) алгоритм для запуска из DFA и построения регулярного выражения такого что , чем в книге Хопкрофта и Уллмана (1979). Там наборы используются для представления наборов строк, которые переводят DFA из состояния в без прохождения через любое состояние, пронумерованное выше . Эта конструкция, хотя и очевидно правильная и очень полезная, является довольно технической. r L ( A ) = L ( r ) R k i j q i q j kArL(A)=L(r)Rijkqiqjk

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

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

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

Janoma
источник
1
Это не другой алгоритм, но алгоритм можно выразить алгебраически, используя ую степень матрицы регулярных выражений в соответствующей алгебре. Возможно, вы найдете это более элегантным / лаконичным. Я ищу ссылку. kRijkk
Макс
1
алгоритм, по существу , вариант алгоритма Флойда-Воршалла для задачи All-пар-кратчайшего пути, так что вы можете найти представление в терминах матрицы умножения на поиск по этим ключевым словам. Rijk
Ян Йоханнсен
2
Я согласен. Это в основном алгоритм Флойда-Варшалла. Он также может быть получен с использованием стандартных методов динамического программирования (как это может сделать Флойд-Варшалл).
Дэвид
Я уверен, что отвечал на такой вопрос раньше, но я не могу его найти.
Рафаэль
@ Макс, не могли бы вы найти ссылку? Меня интересует матричное представление, оно должно быть более привлекательным для алгебры.
Janoma

Ответы:

17

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

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

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

Сильвен
источник
2
Я считаю, что подход к решению уравнений с использованием леммы Ардена является наиболее простым и легким для объяснения, поэтому я представляю его таким образом на начальном уроке теории.
Ян Йоханнсен
Метод системы уравнений звучит блестяще. К сожалению, в библиотеке моего университета нет книги, которую вы упоминаете (Сакарович), но я собираюсь поискать в другом месте.
Janoma
4
Сравнение конструкций также найдено в статье Сакаровича «Язык, выражение и (маленький) автомат», CIAA 2005, LNCS 3845, Springer (2006) 15-30. См. Infres.enst.fr/~jsaka/PUB/Files/LESA.pdf
Герман Грубер
2
Также обратите внимание, что порядок, в котором обрабатываются состояния, может сильно повлиять на размер получаемого регулярного выражения. Это всегда верно: делаете ли вы это с леммой Ардена, МакНотоном-Ямадой, устранением состояния или другим вариантом. Доступно несколько простых эвристик для выбора удачного заказа.
Герман Грубер
15

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

2×2

[abcd]=[(a+bdc)(a+bdc)bd(d+cab)ca(d+cab)]

i,jij

n×na,b,c,dm×mm×(nm)(nm)×m(nm)×(nm)2×22×2

nTfF(T)s,fsT

m=1Rijk

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

mikero
источник
12

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

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

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