python - 可以描述字符串的正则表达式

Question

我有一个字母表 {A, B, C} 和这个字母表上的(大量)单词:
AAABBCABBCCCCAA, ABBBCCC, BBBBCACAC, ...(不同的长度，不同的组合)

我正在寻找一组可以描述这些词的正则表达式(越小越好)。我更喜欢紧凑型((BC)+ 而不是 BCBC)。这不是家庭作业。

1. 执行此操作的好方法是什么？
2. 是否有 Python 包已经可以做到这一点？

我找到了 this question相关。

更新:当我说我更喜欢 (BC)+ 而不是 BCBC 时，我可能有点仓促。我更喜欢使用尽可能少的表达式(在最坏的情况下，每个字符串只有一个正则表达式)，因此优先选择 A+、AA 或 AA+ 之一 来描述 AA(例如)应该取决于其他字符串显示的模式。

Answer 1

如果我对你的问题的理解正确，你有一个字母表和该字母表上的字符串列表，你想构建一个与这些字符串完全匹配的模式。

你或许可以构建一个 deterministic finite automata对于每个字符串，从中构建一个 non-deterministic finite automata那是所有这些的组合 DFA .然后简化 DFA到 NFA .然后只需将 NFA 转换为模式即可。

如果您已经模式化了字符串而不是字符串，这甚至会起作用。但是，不能保证您将获得尽可能小的图案。

我不知道有任何库可以操纵 DFA或 NFA在 Python 中。