汤普森算法中的否定吗？

我在读这对于学习如何写状态机的正则表达式汤普森算法中的否定吗？

但是我只看到像工会，拼接，克莱尼明星，但没有对否定，这就是这里所说的

这是什么结构？

2016-07-23 KaliMa

Thompson是DFA，它不支持负面变换（如果你是这个意思）。 –

你当然不是指DFA，而是NFA（实际上是ε-NFA）。否定的问题是完全有效的，否定前瞻是一个不同的概念，用来模拟第一个。 – akim

汤普森自动机对于否定非常不恰当：它不是确定性的，实际上使用了大量的自发转换（这也是非确定性的来源）。相反，Brzozowski automaton非常适合否定，相交和更一般的所有布尔函数。

你可以玩Vcsn来试验类似的结构。它甚至支持加权表达式和更多的运算符。 This page包含几个示例，显示如何将扩展正则表达式转换为自动机。

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

2016-07-24 09:54:10 akim

我不明白究竟是什么使NFA“不确定”与DFA“确定性”有关。除了DFA只是NFA的更简化版本之外，它们对我而言几乎与我完全一样。您仍然可以在每个节点上进行选择，并沿着有效的路径遍历接受状态。 – KaliMa

我不知道您实际阅读的是什么定义，但首先请注意，根据定义，任何DFA都是NFA。相反，当然，并不成立。因此，例如'0 - a - > 1，0 - a - > 2'在状态0中不确定：有一个选择，可以从状态0进入状态1或状态2，了'。 – akim

是的，但您可以在NFA和DFA中执行此操作 – KaliMa

回答