regex - 为什么 DFA 中不能有多态？

Question

我的问题是，state3 是否也可以命名为 state2，或者一般情况下。为什么我们可以用相同的名称命名我们的州。对于表达式ab+a*a First state 采用“a”。然后它将进入 state2/state3。

Answer 1

有限状态机被定义为包含（除其他外）一组状态，因此对每个状态进行唯一标识是有意义的。状态的命名与它们可能被击中的顺序没有任何关系。

FSM 涉及循环的情况并不少见。一个示例是 FSM 接受具有偶数个 0 的二进制字符串，由下面的状态表表示：

输入 --> | 0 | 1 |
\/--状态 | | |
----------|--------|--------|
状态0 | 状态1 | 状态0 |
状态1 | 状态0 | 状态1 |

状态：{state0，state1}
开始状态：state0
接受状态：{state0}

在这种情况下，机器可能会state0来回移动state1很多次。如果我们每次都必须有一个新的状态，机器的复杂性就会爆炸到无穷大。

Answer 2

你可以随意命名你的状态，只要它们是唯一可识别的。

如果状态没有不同，那么它们首先不应该是两个独立的状态

---

您的特定示例没有任何or-ing，因此您的正则表达式将永远不会使用像那样分支的 DFA。

但是假设你有一个像这样的正则表达式

a(bb | cc), 可以匹配abb或acc

ab并且ac是不同的状态，必须将它们彼此区分开来，并且它们的输出会导致不同的结论。

如果你在ab并且你得到了一个c比你将不得不回到开始，但如果你在这个状态ac并且得到c比你将继续acc并完成。