编译原理习题3-9

✅ 3.9.1

Q（题目）：
扩展图 3.58 的表格，加入下列操作符：

  1. ?（0 次或 1 次）
  2. +（1 次或多次）

Answer（答案）：

节点 n nullable(n) firstpos(n)
n = c₁? true（因为可以为 ε） firstpos(c₁)
n = c₁+ nullable(c₁) firstpos(c₁)

Explanation（解释）：

  • c₁? 表示字符 c₁ 可以出现 0 次或 1 次，因此一定 nullable（可为空）。
  • c₁+ 相当于 c₁c₁*，是否 nullable 取决于第一个 c₁ 是否 nullable。
  • 它们的 firstpos 都来自 c₁，因为第一个出现的位置一定在 c₁ 中。

✅ 3.9.3 ⭐

Q（题目）：
通过构造最小状态的 DFA，证明下列正则表达式是等价的：

  • (a|b)*
  • (a*|b*)*
  • ((ε|a)b*)*

Answer（答案）：
参见 3.7.3 和 3.9.2 中的最小 DFA 图，可知它们都生成相同语言：由任意数量的 a 和 b 组成的字符串，即 Σ*（任意串）。

Explanation（解释）：

这些表达式从形式上不同，但都允许任意数量的 a 和 b 交替、混合、重复，因此它们的最小 DFA 是相同的（只有一个循环状态接收所有输入）。

✅ 3.9.4 ⭐

Q（题目）：
构造下列正则表达式的最小状态 DFA：

  1. (a|b)*a(a|b)
  2. (a|b)*a(a|b)(a|b)
  3. (a|b)*a(a|b)(a|b)(a|b)

是否能发现规律？

Answer（答案）：

  • 每个正则表达式都表示：以任意个 a、b 开头，但必须包含一个特定长度的子串，其中首字符是 a。
  • 每个表达式都必须识别最后一段特定模式。
表达式 最小状态数
1 4 个状态
2 6 个状态
3 8 个状态

Pattern（规律）：

对于正则 (a|b)*a(a|b)ⁿ，DFA 至少需要 2n 个状态：

  • 一个分支状态代表当前匹配到的位置；
  • 一个状态记录历史信息，确保已经看到 “a” 之后的 n 个字符。

✅ 3.9.5 ⭐⭐

Q（题目）：
正式证明：对正则 (a|b)*a(a|b)...(a|b)，其中末尾有 n-1 个 (a|b)，任何 DFA 至少需要 2n 个状态。

Hint 提示：
观察 3.9.4 的模式，每个状态记录了输入的历史信息。

Answer（答案）：

我们构造 DFA 时需要记录：

  • 是否已经匹配到了中间的 'a'（这是转折点）；
  • 接下来读入的每个字符都可能是 a 或 b，必须依次保存；
  • 为了识别到最后一个字符是否完整匹配特定长度的尾串，DFA 需要为每种可能路径分配唯一状态。

因此：

  • 共有 2n 个必要状态：
    • n 个状态记录“未匹配到最后 a”；
    • n 个状态记录“匹配 a 后跟随 k 个字符（0 到 n-1）”。

Conclusion（结论）：

为了处理这种历史相关的匹配任务，必须区分多种前缀路径，DFA 无法通过合并状态减少状态数，因此状态数下界为 2n。