给出识别练习 3.3.2 中各个正则表达式所描述的语言状态转换图。
解答解答步骤：NFA -> DFA -> 最少状态的 DFA（状态转换图）
a(a|b)*a
NFA:
DFA:
NFADFAab{0}AB{1,2,3,5,8}BCD{2,3,4,5,7,8,9}CCD{2,3,5,6,7,8}DCD最少状态的 DFA(状态转换图):
合并不可区分的状态 B 和 D
((ε|a)b*)*
(a|b)*a(a|b)(a|b)
NFA:
DFA:
NFADFAab{0,1,2,4,7}ABC{1,2,3,4,6,7,8,9,11}BDE{1,2,4,5,6,7}CBC{1,2,3,4,6,7,8,9,10,11,13,14,16}DFG{1,2,4,5,6,7,12,13,14,16}EHI{1,2,3,4,6,7,8,9,10,11,13,14,15,16,18}FFG{1,2,4,5,6,7,12,13,14,16,17,18}GHI{1,2,3,4,6,7,8,9,11,15,18}HDE{1,2,4,5,6,7,17,18}IBC最少状态的 DFA(状态转换图):
合并不可区分的状态 A 和 C
a*ba*ba*ba*
3.4.2给出识别练习 3.3.5 中各个正则表达式所描述语言的状态转换图。
3.4.3构造下列串的失效函数。
abababaabaaaaaaabbaabb 解答代码详见：src/failure-function.js
[ 0, 0, 1, 2, 3, 4, 5, 1, 2 ][ 0, 1, 2, 3, 4, 5 ][ 0, 0, 0, 1, 1, 2, 3 ] 3.4.4 ！对 s 进行归纳，证明图 3-19 的算法正确地计算出了失效函数。
图 3-19：计算关键字 b_1b_2…b_n 的失效函数
01 t = 0;02 f(1) = 0;03 for (s = 1; s < n; s ++){04 while( t > 0 && b_s+1 != b_t+1) t = f(t);05 if(b_s+1 == b_t+1){06 t = t + 1;07 f(s + 1) = t;08 }else{09 f(s + 1) = 0;10 }11 } 证明 已知 f(1) = 0在第 1 次 for 循环时，计算 f(2) 的值，当第5行代码 b_2 == b_1 成立时，代码进入到第7行得出 f(2) = 1，不成立时，则代码进入第9行得出 f(2) = 0。显然，这次循环正确的计算出了 f(2) 。假设在第 i-1 次进入循环时，也正确的计算出了 f(i)，也有 f(i) = t (无论 t 是大于 0 还是等于 0)那么在第 1 次进入循环时，分两种情况进行考虑：t == 0
这种情况比较简单，直接从第 5 行开始，当 b_i+1 == b_1 时，f(i+1) = 1，否则 f(i+1) = 0
t > 0
while 循环会不断缩小 t 值，试图找出最大可能的使得 b_i+1 == b_t+1 成立的 t 值，如果找到了，则进入第 5 行执行，得到 f(i+1) = t+1；或者直到 t == 0 时也没有找到，则跳出循环，这时进入第 5 行执行，过程类似于前一种情况。
说明图 3-19 中的第 4 行的复制语句 t = f(t) 最多被执行 n 次。进而说明整个算法的时间复杂度是 O(n)，其中 n 是关键字长度。
解答详见 matrix 的博文 KMP算法详解。
3.4.6应用 KMP 算法判断关键字 ababaa 是否为下面字符串的子串：
abababaababababbaa 解答代码详见：src/failure-function.js
truefalse 3.4.7 ！！说明图 3-20 中的算法可以正确的表示输入关键字是否为一个给定字符串的子串。
图 3-20：KMP 算法在 O(m + n) 的时间内检测字符串a_1a_3…a_n 中是否包含单个关键字 b1b2…bn
s = 0;for(i = 1; i <= m; i ++){ while(s > 0 && a_i != b_s+1) s = f(s); if(a_i == b_s+1) s = s + 1; if(s == n) return "yes";}return "no"; 3.4.8假设已经计算得到函数 f 且他的值存储在一个以 s 为下标的数字中，说明图 3-20 中算法的时间复杂度为 O(m + n)。
解答详见 matrix 的博文 KMP算法详解。
3.4.9Fibonacci 字符串的定义如下：
s1 = bs2 = a当 k > 2 时， sk = sk-1 sk-2例如：s3 = ab, s4 = aba, s5 = abaab
sn 的长度是多少？构造 s6 的失效函数。构造 s7 的失效函数。！！ 说明任何 sn 的失效函数都可以被表示为：f(1) = f(2) = 0，且对于 2 < j <= |sn|, f(j) = j - |sk-1|，其中 k 是使得 |sk| <= j + 1 的最大整数。！！ 在 KMP 算法中，当我们试图确定关键字 sk 是否出现在字符串 sk+1 中，最多会连续多少次调用失效函数？ 解答见 维基百科
s6 = abaababa
failure = [ 0, 0, 1, 1, 2, 3, 2, 3 ]
s7 = abaababaabaab
failure = [ 0, 0, 1, 1, 2, 3, 2, 3, 4, 5, 6, 4, 5 ]