Упростить регулярное выражение в Mathematica

Question

Я недавно узнал о алгебре Клини для манипулирования и упрощения регулярных выражений.

Мне интересно, было ли это встроено в какие-либо вычислительные программы, такие как Mathematica? Было бы здорово иметь вычислительный инструмент для объединения и конкатенации больших выражений и сделать так, чтобы компьютер их упростил.

Если вам неизвестны какие-либо программы со встроенной алгеброй, знаете ли вы какие-либо программы, которые позволяют расширять их движки новыми алгебрами?

Answer 1

Вкл. http://www.maplesoft.com/msw/program/MSW04FinalProgram.pdf, В нем говорится:

Одним из основных результатов теории конечных автоматов является знаменитая теорема Клини, которая утверждает, что язык приемлем конечный автомат тогда и только тогда, когда он может быть представлен регулярным выражение.

и

Основная сложность алгоритмического лечения регулярных выражения, однако, их упрощение. Хотя несколько тождества известны относительно регулярных выражений, например правил алгебры Клини, не существует эффективного алгоритма для решение проблемы упрощения регулярных выражений.

и

В сложившихся обстоятельствах единственный путь - это развитие эвристики. алгоритмы для упрощения регулярных выражений. Для пакета aut, эта статья описывает процедуры Maple Rsimplify, Rabsorb и Rexpand.

Мне интересно, существуют ли реализации с открытым исходным кодом алгоритмов Клиниевой алгебры.