构造与下列正则表达式等价的最小状态的DFA。 (1) 10 | (0|11)0*1 (3) (a|b)*a(a|b)

构造一个与给定正则表达式等价的最小状态有限自动机(DFA)，我们首先需要将正则表达式的结构分解成基本的操作，并找到其中的模式。对于每个例子，我会描述对应的DFA设计：

### 示例1: (1) 10 | (0|11)0*1

这个表达式可以理解为两个部分：10 和 (0|11)0*1。第一个部分是一个固定的字符串"10"，直接对应DFA的一个状态。第二部分表示从0开始，零个或多个11之后跟上一个1，我们可以这样构建：

- 初始状态S0，接受空串；
- 添加一个状态S1，代表匹配到0；
- 添加一个状态S2，代表匹配到11；
- 从S0转移到S1，然后S1可以无限次回退到S0并继续匹配0；
- S1通过读取一个1到达S2；
- S2接着可以无限次匹配0，结束在S1；
- 最后，S2通过读取一个1到达一个新的终止状态S3，这代表匹配到了"10"后的一个1。

DFA图可能看起来像这样：

S0 -> S1 -> [S0] (0)
S1 -> S2 (1)
S2 -> S1 (0)
S2 -> S3 (1)
S3 - terminal

### 示例2: (3) (a|b)*a(a|b)

此表达式表示任意次数的a或b之后跟着一个'a'，然后再跟着任意次数的a或b。可以这样构造：

- 初始状态S0，接受空串；
- 添加状态S1、S2分别代表匹配"a"和"b";
- S1和S2之间互相转移，代表任意次数的交替；
- 添加状态S3，只接受'a';
- 从S0出发，先经过任意次数的S1/S2，然后到达S3匹配'a';
- 从S3出发，可以再次进入S1/S2匹配(a|b)，直到到达一个新的终端状态S4。

DFA图可能如下所示：

S0 -> [S1,S2] (a,b)
S1 -> S1 (a)
S1 -> S3 (a)
S2 -> S2 (b)
S2 -> S3 (b)
S3 -> S1 (a)
S3 -> S2 (b)
S3 -> S4 (a) // 新状态
S4 - terminal