1.构造下列正规式相应的 DF Ａ:(1) １（0|1）*１ 01(2) 1(1010＊ | 1(0 １ 0）* 1)* 0(3) a((a|ｂ)*|ab*a)* b(4) b((ａ b)* ｜ bb)* ａｂ

考查要点：本题要求根据给定的正规式构造对应的确定有限自动机（DFA）。
解题核心思路：

1. 正规式分解：将正规式按运算符（如|、*、连接）分解为基本结构。
2. NFA构造：根据分解后的结构，构造非确定有限自动机（NFA）。
3. 子集法转换：通过子集法将NFA转换为DFA，消除非确定性。
   关键点：

• 正确定义状态转移，尤其是处理*运算符的循环结构。
• 合并等价状态，确保DFA的最小化（本题未要求最小化，但需保证正确性）。

第（1）题：正规式 1(0|1)*101

分解正规式结构

正规式可分解为：

1. 初始部分：读取字符 1。
2. 循环部分：任意次数（包括0次）的 0 或 1（即 (0|1)*）。
3. 结尾部分：固定读取 101。

构造NFA

• 状态定义：
  • S：初始状态，读取第一个 1 后进入中间状态 A。
  • A：循环状态，读取 0 或 1 后保留在自身，或读取 1 进入状态 B（开始匹配 101）。
  • B：匹配 101 的中间状态，读取 0 后进入状态 C，读取 1 则失败。
  • C：读取最后一个 1 后进入接受状态 D。
  • D：接受状态。

转换为DFA

通过子集法合并NFA状态，消除非确定性。最终DFA状态如下：

• 状态0：初始状态，对应NFA的 S。
• 状态1：读取第一个 1 后进入，对应NFA的 A。
• 状态2：读取后续 0 或 1 时循环，对应NFA的 A 的闭包。
• 状态3：匹配到 10 时进入，对应NFA的 B。
• 状态4：匹配到 101 时进入，对应NFA的 D（接受状态）。