(9)请构造正规式1(0|1)*101的DFA，并将其最小化。

考查要点：本题要求根据给定的正规式构造对应的确定有限自动机（DFA），并将其最小化。主要考查学生对正规式到DFA转换方法的掌握，以及DFA状态最小化的理解与应用。

解题核心思路：

1. 正规式分析：将正规式分解为关键部分（如起始符1、中间任意字符序列(0|1)*、结尾101），设计状态转移逻辑。
2. 状态设计：通过状态表示匹配进度，如初始状态、中间任意字符处理状态、结尾匹配状态等。
3. 陷阱状态：处理无法继续匹配的情况，所有输入均保留在陷阱状态。
4. 最小化：通过状态等价性判断，合并不可区分的状态，确保DFA状态数最少。

破题关键点：

• 状态转移逻辑需严格对应正规式结构，确保所有可能输入路径被正确处理。
• 陷阱状态的引入可简化无法继续匹配的分支。
• 最小化过程需验证状态间的转移和接受属性是否等价。

步骤1：分析正规式结构

正规式 1(0|1)*101 的结构为：

1. 起始符1：必须以1开头。
2. *中间任意字符序列`(0|1)**：允许任意数量的0或1`。
3. 结尾101：必须以101结尾。

步骤2：设计DFA状态

• q0（初始状态）：等待读取起始符1。
• q1：已读起始符1，处理中间任意字符。
• q2：中间序列结束后，开始匹配结尾1。
• q3：匹配到1后的0。
• q4（接受状态）：匹配到101的最后一个1。
• q5（陷阱状态）：无法继续匹配时进入，所有输入均保留在q5。

步骤3：构建转移表

步骤4：DFA最小化

• 状态等价性判断：所有状态在转移和接受属性上均不可区分，因此无法合并，DFA已是最小化形式。