• Introduction
• 1. 1.Introduction
• 2. 2.A Simple Syntax-Directed Translator
• 3. 3.Lexical Analysis
• 4. 4.Syntax Analysis
• 5. 5.Syntax-Directed Translation
• 6. 6.Intermediate-Code Generation
• 7. 7.Run-Time Environments
• 8. 8.Code Generation
• 9. 12.InterProcedural Analysis
• Published with GitBook

# 3.4 节的练习

### 3.4.1

#### 解答

1. a(a|b)*a

NFA:

DFA:

NFA DFA a b
{0} A B
{1,2,3,5,8} B C D
{2,3,4,5,7,8,9} C C D
{2,3,5,6,7,8} D C D

``````最少状态的 DFA(状态转换图):

![3 4 1-1](assets/3.4.1-1.gif)
``````
1. ((ε|a)b*)*

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

NFA:

``````DFA:

<table>
<tr>
<th>NFA</th>
<th>DFA</th>
<th>a</th>
<th>b</th>
</tr>
<tbody>
<tr>
<td>{0,1,2,4,7}</td>
<td>A</td>
<td>B</td>
<td>C</td>
</tr>
<tr>
<td>{1,2,3,4,6,7,8,9,11}</td>
<td>B</td>
<td>D</td>
<td>E</td>
</tr>
<tr>
<td>{1,2,4,5,6,7}</td>
<td>C</td>
<td>B</td>
<td>C</td>
</tr>
<tr>
<td>{1,2,3,4,6,7,8,9,10,11,13,14,16}</td>
<td>D</td>
<td><b>F</b></td>
<td><b>G</b></td>
</tr>
<tr>
<td>{1,2,4,5,6,7,12,13,14,16}</td>
<td>E</td>
<td><b>H</b></td>
<td><b>I</b></td>
</tr>
<tr>
<td>{1,2,3,4,6,7,8,9,10,11,13,14,15,16,<b>18</b>}</td>
<td><b>F</b></td>
<td><b>F</b></td>
<td><b>G</b></td>
</tr>
<tr>
<td>{1,2,4,5,6,7,12,13,14,16,17,<b>18</b>}</td>
<td><b>G</b></td>
<td><b>H</b></td>
<td><b>I</b></td>
</tr>
<tr>
<td>{1,2,3,4,6,7,8,9,11,15,<b>18</b>}</td>
<td><b>H</b></td>
<td>D</td>
<td>E</td>
</tr>
<tr>
<td>{1,2,4,5,6,7,17,<b>18</b>}</td>
<td><b>I</b></td>
<td>B</td>
<td>C</td>
</tr>
</tbody>
</table>

![3 4 1-3](assets/3.4.1-3.gif)
``````
1. a*ba*ba*ba*

### 3.4.3

1. abababaab
2. aaaaaa
3. abbaabb

#### 解答

1. [ 0, 0, 1, 2, 3, 4, 5, 1, 2 ]
2. [ 0, 1, 2, 3, 4, 5 ]
3. [ 0, 0, 0, 1, 1, 2, 3 ]

### 3.4.4 ！

``````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  }
``````

#### 证明

1. 已知 f(1) = 0
2. 在第 1 次 for 循环时，计算 f(2) 的值，当第5行代码 b_2 == b_1 成立时，代码进入到第7行得出 f(2) = 1，不成立时，则代码进入第9行得出 f(2) = 0。显然，这次循环正确的计算出了 f(2) 。
3. 假设在第 i-1 次进入循环时，也正确的计算出了 f(i)，也有 f(i) = t (无论 t 是大于 0 还是等于 0)
4. 那么在第 1 次进入循环时，分两种情况进行考虑：

1. t == 0

这种情况比较简单，直接从第 5 行开始，当 b_i+1 == b_1 时，f(i+1) = 1，否则 f(i+1) = 0

2. t > 0 while 循环会不断缩小 t 值，试图找出最大可能的使得 b_i+1 == b_t+1 成立的 t 值，如果找到了，则进入第 5 行执行，得到 f(i+1) = t+1；或者直到 t == 0 时也没有找到，则跳出循环，这时进入第 5 行执行，过程类似于前一种情况。

1. abababaab
2. abababbaa

1. true
2. false

### 3.4.7 ！！

``````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.9

Fibonacci 字符串的定义如下：

1. s1 = b
2. s2 = a
3. 当 k > 2 时， sk = sk-1 sk-2

1. sn 的长度是多少？
2. 构造 s6 的失效函数。
3. 构造 s7 的失效函数。
4. ！！ 说明任何 sn 的失效函数都可以被表示为：f(1) = f(2) = 0，且对于 2 < j <= |sn|, f(j) = j - |sk-1|，其中 k 是使得 |sk| <= j + 1 的最大整数。
5. ！！ 在 KMP 算法中，当我们试图确定关键字 sk 是否出现在字符串 sk+1 中，最多会连续多少次调用失效函数？

#### 解答

1. 维基百科
2. s6 = abaababa

failure = [ 0, 0, 1, 1, 2, 3, 2, 3 ]

3. s7 = abaababaabaab

failure = [ 0, 0, 1, 1, 2, 3, 2, 3, 4, 5, 6, 4, 5 ]