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

3.6 节的练习

3.6.1 !

3.4 节的练习中图 3-19 计算了 KMP 算法的失效函数。说明在已知失效函数的情况下,如何根据已知的关键字 b_1b_2…b_n 构造出一个具有 n+1 个状态的 DFA,该 DFA 可以识别语言 .*b_1b_2…b_n 。更近一步,证明构造这个 DFA 的时间复杂度为 O(n)。

解答

为方便说明,以 3.4.3-3 的字符串 abbaabb 为例,失效函数为:

  • n : 1, 2, 3, 4, 5, 6, 7
  • f(n): 0, 0, 0, 1, 1, 2, 3

构造得到的 DFA 为:

3 6 1

构造这个 DFA 的伪代码为:

for (i = 0; i< n; i ++) {
    move[s[i], c] = {
        if ( c == b_1b_2…b_n[i] ) {
            goto s[i+1]
        } else {
            goto s[f(i)]
        }
    }
}

很显然,在已知 f(n) 的情况下,该算法的时间复杂度为 O(n)

3.6.2

为练习 3.3.5 中的每个语言设计一个 DFA 或 NFA。

3.6.3

找出图 3-29 所示的 NFA 中所有标号为 aabb 的路径。这个 NFA 接受 aabb 吗?

解答

  • (0) -a-> (1) -a-> (2) -b-> (2) -b-> ((3))
  • (0) -a-> (0) -a-> (0) -b-> (0) -b-> (0)
  • (0) -a-> (0) -a-> (1) -b-> (1) -b-> (1)
  • (0) -a-> (1) -a-> (1) -b-> (1) -b-> (1)
  • (0) -a-> (1) -a-> (2) -b-> (2) -b-> (2)
  • (0) -a-> (1) -a-> (2) -b-> (2) -ε-> (0) -b-> (0)
  • (0) -a-> (1) -a-> (2) -ε-> (0) -b-> (0) -b-> (0)

该 NFA 显然接受 aabb

3.6.4

对于图 3-30 的 NFA,重复练习 3.6.3

3.6.5

给出如下练习中的 NFA 的转换表:

  1. 练习 3.6.3
  2. 练习 3.6.4
  3. 图 3-26

解答

表1

状态 a b ε
0 {0,1} {0}
1 {1,2} {1}
2 {2} {2,3} {0}
3

表2

状态 a b ε
0 {1} {3}
1 {2} {0}
2 {3} {1}
3 {0} {2}

表3

状态 a b ε
0 {1,2}
1 {2}
2 {2}
3 {4}
4 {4}