regex - 汤普森算法的否定？

Question

我读这篇文章是为了学习如何为正则表达式编写状态机

https://en.wikipedia.org/wiki/Thompson%27s_construction

但是我只看到并集，串联，Kleene star之类的东西，而没有看到这里提到的否定

https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton#Closure_properties

它的结构是什么？

Answer 1

Thompson 自动机非常不适合否定:它不是确定性的并且实际上使用了大量的自发转换(这也是不确定性的来源)。相反，Brzozowski automaton非常适合取反、交集以及更普遍的所有 bool 函数。

您可以使用 Vcsn 来尝试类似的结构。它实际上什至支持加权表达式和更多的运算符。 This page包含几个示例，展示如何将扩展的正则表达式转换为自动机。

Redgrep实现 Brzozowski 方法。在 this very nice video设计师解释了这是如何工作的。