computation-theory - (0+1)* 的 DFA 是多少？

Question

我在下面画了这张图。但我想确定答案，因为 + 和 * 运算符令人困惑。

     _  
    | \
--> q_|- 0,1,E

这里我的 DFA 只有一个状态 q。0,1,empty 都被重定向到 q 本身。

Answer 1

(0+1) 表示您可以选择0 或 1 但不能同时选择两者。+ 类似于 OR。星号表示您可以进行此选择零次或多次。

因此， (0+1)* 将包括任何 0 和 1 的字符串，包括空字符串。

Answer 2

晚了5年，但这是我得到的：

Start at A. A is also an end state.

From A: Input 0 goes to B. B is an end state.
        Input 1 goes to C. C is an end state.

From B: Input 0 goes to B.
        Input 1 goes to C.

From C: Input 0 goes to B.
        Input 1 goes to C.

我很确定这是正确的（为考试自动取款机学习）......

可能很难从中形象化，但是如果您根据我的说明绘制图表，应该会更清楚。

希望这可以帮助任何查找此内容的人。