Simplify Regular Expression in Mathematica

问题:

I recently found out about Kleene algebra for manipulating and simplifying regular expressions.

I'm wondering if this has been build into any computational software programs like Mathematica? It would be great to have a computational tool for doing unions and concatenations of large expressions and have the computer simplify them.

If you are not aware of any programs with this algebra built in, do you know any programs that allow extending their engines with new algebras?

回答1:

On http://www.maplesoft.com/msw/program/MSW04FinalProgram.pdf, it states:

One of the basic results of the theory of finite automata is the famous Kleene theorem, which states that a language is acceptable by a finite automaton if and only if it can be represented by a regular expression.

and

The main difficulty of the algorithmic treatment of regular expressions is, however, their simplification. Although several identities are known concerning regular expressions, e.g., the rules of Kleene algebra, there does not exist an effective algorithm for solving the simplification problem of regular expressions.

and

Under the circumstances, the only way left is to develop heuristic algorithms for simplifying regular expressions. For the aut package, this paper outlines the Maple procedures Rsimplify, Rabsorb and Rexpand.

Im wondering if open-source implementations of Kleene Algebra algorithms exist.