(b) G = ({A, S}, {0,1}, S, P) P: S A
NLPR, CASIA
0A0 | 1A1 0A0 | 1A1 | ε
2004-3-6
9
NLPR
第三章习题解答
3-2. 有以下文法：G = ({S,B,C},{a,b,c},P, S),其中： P: S → aSBC | abC bB → bb cC → cc 求 L(G)=? CB → BC bC → bc
x
p(x) 证明： H( p, q) = H( p) + D( p || q) = H( p) + ∑ p(x) log q(x) x∈X
= −∑ p(x) log p(x) + ∑ p(x)(logp(x) − logq(x))
x∈X x∈X
= −∑ p( x) logq( x)
x∈X
NLPR, CASIA
p ( x) D( p || q) = ∑ p( x) log q ( x) x∈X
NLPR, CASIA
2004-3-6
6
NLPR
第二章习题解答
2-3. 举例说明（任意找两个分布 p 和 q ），KL 距离是不对 称的，即 D(p || q) ≠ D(q || p)。 （略）
NLPR, CASIA
NLPR, CASIA 2004-3-6
10
NLPR
第三章习题解答
3-3. 设文法 G 由如下规则定义： S → AB A → Aa|bB B → a|Sb 给出下列句子形式的派生树: (1)baabaab (2)bBABb 解： (1) A A b B a b
NLPR, CASIA
S B a A B a
H ( X ) = − ∑ p( x) log 2 p( x)
x∈X
NLPR, CASIA
2004-3-6
5
NLPR
第二章习题解答
2-2. 任意取另外一段文字，按上述同样的方法计算字符分布 的概率，然后计算两段文字中字符分布的 KL 距离。 解：设两段文字字符的概率分布分别为 p(x) 和 q(x)，其 KL (Kullback-Leibler) 距离（相对熵）为：
2004-3-6
7பைடு நூலகம்
NLPR
第二章习题解答
2-4. 设 X ~ p(x)，q(x) 为用于近似 p(x) 的一个概率分布，则 p(x) 与 q(x) 的交叉熵定义为 H(p, q) = H(p) + D(p || q)。 请证明：
H ( p , q ) = − ∑ p ( x ) log q ( x )
NLPR, CASIA 2004-3-6
3
NLPR
第一章习题解答
1-3. 思考一下，如果用计算机编译技术中程序设计语言的某一 句法分析方法直接解析普通的英文句子，会存在什么问 题？ (1) 句法结构的歧义问题 (2) 句法规则的合法性，例如，LR分析方法，LR表中出 现冲突项目。 (3) 异常处理 1-4. 思考一下，你的大脑理解一个英文句子的基本过程。 （略）
NLPR, CASIA
2004-3-6
2
NLPR
第一章习题解答
1-2. 试比较汉语和英文句子中地点状语位置的差异。 (1) 汉语句子中的地点状语一般在谓语动词的前面，而 英语句子中的地点状语一般在谓语动词的后面。 如：我在北京大学学习。 I am studying in Peking University. (2) 地点状语是偏正短语时，汉语中一般范围大的在前 （左）面，范围越小、越具体的修饰词离中心词越近，英 文中正好相反。 如：他在三层左边那个屋子里的桌子上放了一本书。 He put a book on the desk in the left room of the third floor.
自然语言理解
( App)
宗成庆 中科院自动化研究所 模式识别国家重点实验室
cqzong@ /English/cip/cqzong.htm
No.95, Zhongguancun East Road Beijing 100080, China Tel. No.: +86-10-6255 4263
2004-3-6
8
NLPR
第三章习题解答
3-1. 构造上下文无关文法用以产生： (a) 有相同数目的 0 和 1 的所有 0, 1 符号串。 (b) {a1a2…anan…a2a1|ai∈{0,1}, 1≤ i ≤n}。 解: (a) G = ({A, B, S}, {0,1}, S, P) P: S 0B | 1A A 0S |1AA| 0 B 1S |0BB| 1
NLPR
第一章习题解答
1-1. 说明如下句子有多少种不同的含义？ (1) Time flies like an arrow. (a) 光阴似箭。 (b) 时间苍蝇喜欢箭。 (2) He drew one card. (a) 他画一张卡片。 (3) 咬死猎人的狗。 (a) 一只狗把猎人咬死了。 (b) ××把猎人的狗咬死。 (b) 他拉一张纸牌。
解： S ⇒ aSBC ⇒ aaSBCBC ⇒ aaabCBCBC ⇒ a3bCBCBC ⇒ a3bBCCBC ⇒ a3bbCCBC ⇒ a3bbCBCC ⇒a3bbBCCC ⇒ a3bbbCCC ⇒ a3b3cCC ⇒a3b3ccC ⇒a3b3c3 …… L(G) = {anbncn | n ≥ 1}
12
NLPR
Thanks
谢谢!
NLPR, CASIA
2004-3-6
13
NLPR, CASIA 2004-3-6
4
NLPR
第二章习题解答
2-1. 任意摘录一段文字，统计这段文字中所有字符的相对频 率。假设这些相对频率就是这些字符的概率，请计算其 分布的熵。 解：设 X 是字符集，字符 x 的概率分布为 p(x) = P(X = x)，x ∈ X。X 的熵 H(X) 为：
2004-3-6
(2) 略 b B a
11
S
NLPR
第三章习题解答
3-4. 写一个程序模拟一个确定性的 PDA。 参阅 PDA 的定义及其工作原理。 3-5. 写一个程序以正则文法 G 作为输入，构造 G 相应的有限 自动机。 参阅由正则文法构造有限自动机的一般步骤。
NLPR, CASIA
2004-3-6