二进制串正则表达式有效性验证及简化问询（含指定DFA）

首先，我们先明确这个DFA的行为：

• 起始状态q0，输入0直接进入陷阱状态q3（一旦进入就无法再到达接受状态），输入1到q1；
• q1输入0到接受状态q2，输入1进入陷阱q3；
• q2输入0或1都回到q0；
• q3输入任何字符都停留在q3。

由此可以推导，DFA接受的语言是所有以10结尾，且每一段10之后只能跟一个0或1（之后必须再跟10）的二进制字符串，简单来说就是形如(10(0|1))^n 10（n≥0）的字符串，比如10、10010、10110、10010010等。

给定正则表达式的有效性 #

你提供的正则表达式是(10) ∪ ((10(0 ∪ 1))*10)，我们可以拆解来看：

• 第一部分10对应最短的合法字符串；
• 第二部分(10(0 ∪ 1))*10表示任意次重复10后跟一个0或1，最后再以10结尾。

注意到(10(0|1))*包含了空串（重复0次的情况），此时第二部分就等价于10，和第一部分完全重复。因此整个表达式描述的语言和DFA接受的语言完全一致，是该语言的有效正则表达式。

正则表达式的简化 #

我们可以直接去掉重复的部分，将原表达式简化为：

(10(0|1))*10

如果想要更直观地体现“以10开头，后续重复(0|1)10”的结构，还可以等价改写为：

10((0|1)10)*

这两种简化形式都和原表达式等价，且更简洁易读。

内容的提问来源于stack exchange，提问作者eagle37