正则表达式 0(0+1)*0+1(0+1)*1 的 DFA 是多少？

Question

这是我画的DFA-

正确吗？
我很困惑，因为

q4

状态对于同一输入符号有

2

不同的转换，这违反了

DFA

的规则，但我想不出任何其他解决方案。

Answer 1

您的 DFA 不正确。
_{你的 DFA 完全错误，所以我不发表评论}

RE 的 DFA：

0(1 + 0)*0 + 1(1 + 0)*1  

语言描述：如果字符串以

0

开头，则应以

0

结尾，或者如果字符串以

1

开头，则应以

1

结尾。因此有两个最终状态（state-5、state-4）。

state-4：接受

1(1 + 0)*1

状态 5：接受

0(1 + 0)*0

state-1：开始状态。

DFA：

编辑：

正则表达式中的

+ 运算符

(0 + 1)* = (1 + 0)*

是由

1

和

0

组成的任何字符串，包括空字符串

^

。

这里

+

表示并集，如果它出现在两个 RE: 之间，并且

A U B = B U A

（类似地）=>

(0 + 1) = (0 + 1)

。

_加号

+

的含义取决于它出现的语法：如果表达式是a⁺（

+

是上标），这意味着多个

a

之一，如果

a+b

那么

+

意味着并集操作

a

或

b

。

a+ : { a, aa, aaa, aaa.....}

是具有

a

的语言中任意数量的

length > 1

字符串。

Answer 2

我认为你应该先从0开始

0(1 + 0)*0 + 1(1 + 0)*1

Answer 3

绘制确定性有限自动机：

1. (0+1)101(0+1)
2. 10(0+1)*1