Chp-03-形式语言与自动机.pdf

第3章 形式语言与自动机 及其在NLP中的应用 北京市海淀区中关村东路95号 电话：+86-10-8254 4688 邮编：100190 邮件：cqzong@nlpr.ia.ac.cn 3.1 基本概念 宗成庆： 《自然语言理解》讲义，第 3 章 2/119 3.1 基本概念 树(tree) ：  树是一种数据结构。  一个连通的无回路的无向图称为树(或称自由树) 。  如果树中有一个结点被特别地标记，则这棵树被 称之为根树，这个被特别标记的结点被称之为根 结点。 宗成庆： 《自然语言理解》讲义，第 3 章 3/119 3.1 基本概念 根结点 A A C 中间(内) B C 结点 B D E (a) (b) 叶结点 D E (c) 父结点: A 是B、C 结点的父结点；C是D、E 的父结点。 子结点：B、C 是A 的子结点；D、E 是C 的子结点。 兄弟结点：B、C 互为兄弟结点；D、E 互为兄弟结点。 宗成庆： 《自然语言理解》讲义，第 3 章 4/119 3.1 基本概念 字符串(string)  定义：假定 是字符的有限集合，由 中字符 相连而成的有限序列被称之为 上的字符串(或 称符号串，或称链) 。特殊地，不包括任何字符 的字符串称为空串，记作 。  符号串的长度：符号串中符号的个数。符号串x 的长度用|x|表示。|| = 0。 包括空串的 上字符串的全体记为* 。 宗成庆： 《自然语言理解》讲义，第 3 章 5/119 3.1 基本概念 字符串操作 假定 是字符的有限集合，x, y 是上的符号串 (1) 字符串连接：则把 y 的各个符号写在 x 的符号之 后得到的符号串称为x 与y 的连接，记作xy 。 例如： ={a, b, c}, x=ab, y=cba 那么，xy=abcba 宗成庆： 《自然语言理解》讲义，第 3 章 6/119 3.1 基本概念  设x是符号串，把x 自身连接n 次得到的符号串， n 即z=xx…x (n个x), 称为x 的n 次方幂，记作x 。 0  注意：x =