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