Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
117 lines (79 sloc) 3.04 KB

3.9 节的练习

3.9.1

扩展图 3-58 中的表,使得它包含如下运算符:

解答

节点n nullable(n) firstpos(n)
n = c_1 ? true firstpos(c_1)
n = c_1 + nullable(c_1) firstpos(c_1)

3.9.2

使用算法 3.26 将练习 3.7.3 中的正则表达式直接转换成 DFA。

解答

  1. (a|b)*

    • (a|b)*# 的抽象语法树

      3 9 2-1-1

    • (a|b)*# 的语法分析树的节点的 nullable, firstpos 和 lastpos

      3 9 2-1-2

    • 函数 followpos

      位置n followpos(n)
      1 {1, 2, 3}
      2 {1, 2, 3}
      3
    • 计算步骤

      这棵树的根节点的 firstpos 的值是 {1, 2, 3},因此 D 的开始状态就是这个集合,令 A = {1, 2, 3}。计算 Dtran[A, a] 和 Dtran[A, b], 在 A 的位置中,位置 1 对应于 a,而 2 对应于 b。因此 Dtran[A, a] = followpos(1) = {1, 2, 3}, Dtran[A, b] = followpos(2) = {1, 2, 3}。 两者结果均为集合 A,本次计算未产生新状态,计算结束。

    • DFA

      3 9 2-1-dfa

  2. (a*|b*)*

  3. ((ε|a)|b*)*

  4. (a|b)*abb(a|b)*

3.9.3 !

我们只需要说明两个正则表达式的最少状态 DFA 同构,就可以证明这两个正则表达式等价。使用这种方法来证明下面的正则表达式 (a|b)*, (a*|b*)* 以及 ((ε|a)b*)* 相互等价。注意:可利用练习 3.7.3 中构造出的这些表达式的 DFA。

解答

见 3.7.3 的解答和 3.9.2-1 的解答

3.9.4 !

为下列正则表达式构造出最少状态的 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)

它们有何规律?

3.9.5 !!

为证明例 3.25 中非正式的结论,说明正则表达式

(a|b)*a(a|b)...(a|b)

的任何 DFA 至少具有 2^n 个状态。在这个正则表达式中, (a|b) 在其尾部出现了 n-1 次。提示:观察练习 3.9.4 中的规律。各个状态分别表示了关于已输入串的哪些信息?