我正在研究接受正常语言的给定采样的学习状态机，您可以在采样中允许或禁止噪声，为简单起见，假设没有噪声。
示例：
给定字符串['fun'，'gun']，我可以构造正则表达式'fun | gun'，但是更短的正则表达式描述为'[fg] un'，我希望系统地找到它。
我看过一些论文，它们向RNN讲授语言，然后以各种近似的怪异方式从RNN提取状态机，这有点奇怪，因为我似乎还从计算机科学的时代模糊地记住了优化状态机是一个经过充分研究和解决的问题。如果第二个是正确的，为什么不简单地从任何接受该语言的状态机开始，然后根据状态或某些条件对其进行优化？
总之有python中的任何正则表达式/状态机优化算法，我可以在一些晦涩的软件包中使用，因为我没有设法找到算法或实现该软件包的软件包，只是一些模糊的CS讲座幻灯片。
最小化正则表达式和最小化状态机是非常不同的问题。的确，尽管DFA和正则表达式具有同等的表现力（它们可以描述完全相同的语言），但表示形式的大小之间并没有简单的关系。有些DFA需要在状态数中使用大小指数的正则表达式，而当转换为DFA时（即使最小化），其正则表达式也会呈指数级膨胀。而且，与最小化DFA中的状态不同，最小化正则表达式的大小基本上是很难的。 （有“大约最少”的算法，但是它们并不漂亮。）
标准Python库中没有软件包可以执行这些任务。 Internet上存在大量不良且受复制保护的实现（有时甚至是二合一）；由于某种原因，几乎所有的实现似乎都是由仍在学习所用语言的学生或认为自己的工作过于珍贵而无法作为开源共享的学者来完成的。无论如何，前面的贪吃蛇是为什么SO劝阻“向我找资源”问题的一个例子：他们倾向于吸引那些对任何人都没有特别帮助的自以为是的回答（也许会挠挠响应者的痒）。 >
如果您要对其进行编程，则算法实际上非常简单。将正则表达式转换为NFA的Thompson结构不应超过Python的一百行，而生成DFA的powerset结构甚至更简单。获得NFA-> DFA后，您可以使用Brzozowski的算法进行最小化，该算法很简单：将DFA反转生成NFA，将其还原为DFA，然后反转并再次还原。尚不清楚该方法为何起作用，但它确实起作用，并且在编写DFA反向器后只需一行代码，而这又是六行代码。