Недавно я узнал о алгебре Клине для манипулирования и упрощения регулярных выражений.
Мне интересно, если бы это было встроено в любые вычислительные программы, такие как Mathematica? Было бы здорово иметь вычислительный инструмент для объединения и конкатенации больших выражений и упростить их компьютер.
Если вам неизвестны какие-либо программы с этой встроенной алгеброй, знаете ли вы какие-либо программы, которые позволяют расширять их двигатели новыми алгебрами?
В http://www.maplesoft.com/msw/program/MSW04FinalProgram.pdf говорится:
Одним из основных результатов теории конечных автоматов является известная теорема Клини, в которой говорится, что язык приемлем конечный автомат тогда и только тогда, когда его можно представить регулярным выражение.
и
Основная трудность алгоритмического лечения регулярных выражения, однако, являются их упрощением. Хотя несколько известны идентичности относительно регулярных выражений, например, правила алгебры Клейена, не существует эффективного алгоритма для решение проблемы упрощения регулярных выражений.
и
В сложившихся обстоятельствах единственный путь - это разработать эвристику алгоритмы для упрощения регулярных выражений. Для пакета
autв этой статье описываются процедуры Maple Rsimplify, Rabsorb и Rexpand.
Мне интересно, существуют ли алгоритмы алгоритмов Клейн Алгебры с открытым исходным кодом.