【自然语言处理综论】 002 正则表达式与自动机

词汇的计算机处理

1. 单词的拼写模型
2. 单词的发音模型
3. 单词的形态模型
4. 自动语音识别 ASR
5. 文本-语音合成 TTS
6. 拼写错误矫正

---

正则表达式与自动机

正则表达式是字符文本序列的标准记录方式

有限状态自动机不仅是用来实现正则表达式的数学工具，而且也是计算语言学中最有用的工具

正则表达式

正则表达式语言是模式匹配的有力工具

正则表达式的基本运算包括符号的毗连、符号的析取、计数符、锚号、前后关系运算

任何正则表达式都可以实现为一个有限状态自动机

自动机

自动机的表示形式

1. 有向图
2. 状态转移表

从形式上说，一个有限状态自动机可以用5个参数来定义

1. $Q$: $N$中状态$q_0, q_1, … q_N$的有限集合
2. $\Sigma$: 有限的输入符号字母表
3. $q_0$: 初始状态
4. $F$: 终极状态的集合 $F \subseteq Q$
5. $\delta (q, i)$: 状态之间的转移函数或者转移矩阵。给定一个状态$q \in Q$和一个输入符号$i \in \Sigma, \delta (q, i)$返回一个新的状态$q’ \in Q$，因此，$\delta (q, i)$是从$Q \times \Sigma$到$Q$的一个关系

• 形式语言：它是一个模型，这个模型能够而且只能够生成或者识别满足形式语言定义所要求的某一种形式语言的字符串

非确定有限状态自动机

确定自动机和非确定自动机的关系：

正则语言与FSA：

---

这一部分之前看过，所以只是简单过一遍