简化Mathematica中的正则表达式

Question

我最近发现了关于Kleene代数的操作和简化正则表达式.

我想知道这是否已经构建到像Mathematica这样的计算软件程序中？拥有一个用于进行大型表达式的联合和连接的计算工具并让计算机简化它们将会很棒.

如果您不了解内置此代数的任何程序,您是否知道任何允许使用新代数扩展其引擎的程序？

Answer 1

在http://www.maplesoft.com/msw/program/MSW04FinalProgram.pdf上,它声明:

有限自动机理论的基本结果之一是着名的Kleene定理,该定理指出一种语言是有限自动机可接受的,当且仅当它可以用正则表达式表示时.

和

然而,正则表达式的算法处理的主要困难是它们的简化.尽管已知关于正则表达式的若干身份,例如Kleene代数的规则,但是不存在用于解决正则表达式的简化问题的有效算法.

和

在这种情况下,剩下的唯一方法是开发启发式算法来简化正则表达式.对于aut包,本文概述了Maple过程Rmplmplify,Rabsorb和Rexpand.

我想知道是否存在Kleene Algebra算法的开源实现.