6. 令 $A$、$B$ 和 $C$ 是任意正规式，证明以下关系成立。#

(1) $A | A = A$

(2) $(A^*)^* = A^*$

(3) $A^* = \varepsilon | AA^*$

(4) $(AB)^*A = A(BA)^*$

$A = b | aA 当且仅当 A = a * b$

---

7. 构造下列正规式相应的 DFA。#

(1) $1(0|1)^*101$

(3) $0^*10^*10^*10^*$

---

8. 给出下面正规表达式。#

(1) 以 01 结尾的二进制数串。

(2) 能被 5 整除的十进制整数。

(3) 包含奇数个 1 或奇数个 0 的二进制数串。

---

9. 对下面情况给出 DFA 及正规表达式。#

(1) $\{0,1\}$ 上含子串 010 的所有串。

---

12. 将图 3.19 中的有限自动机分别确定化和最少化。#

(注：以下为图 3.19 中自动机的文字描述，方便您参考)

(a) 需确定化的有限自动机：

• 初始状态/接受状态 ：0
• 状态转移 ：
• 状态 0：接收 a 转移到 0；接收 a, b 转移到 1。
• 状态 1：接收 a 转移到 0。

(b) 需最小化的有限自动机：

• 初始状态 ：0
• 接受状态 ：0, 1
• 状态转移 ：
• 状态 0：接收 a 转移到 1；接收 b 转移到 2。
• 状态 1：接收 a 转移到 1；接收 b 转移到 4。
• 状态 2：接收 a 转移到 1；接收 b 转移到 3。
• 状态 3：接收 a 转移到 3；接收 b 转移到 2。
• 状态 4：接收 a 转移到 0；接收 b 转移到 5。
• 状态 5：接收 a 转移到 5；接收 b 转移到 4。