《有限自动机理论》

发表于   |   分类于 计算机图书 , 读书笔记   |   暂无评论

第1章 基础知识

1.1 集合及其运算

幂集: $A$ 的所有子集组成的集合, 称为 $A$ 的幂集.
对于一个含有 $n$ 个元素的集合, 选出 $k$ 个元素组成子集的个数可以表示成: $\displaystyle (1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k$

1.2 关系

集合 $A, B$ 之间的关系 $R={(a,b)| a \in A, b \in B, a,b \mbox{ 满足其他指定条件}}$. 若 $(a,b)\in R$, 则记 $aRb$.
等价关系: $R$ 是集合 $A$ 上的等价关系, $a,b,c \in A$, 若同时满足:

  1. (自反性) $aRa$
  2. (对称性) $aRb \Rightarrow bRa$
  3. (传递性) $aRb, bRc \Rightarrow aRc$

关系的合成: $R_1 \circ R_2={ (a,c) | (a,b) \in R_1, (b,c) \in R2 }$
关系的幂: $R^0 = { (a,a) | a \in A }, R^n = R{n-1} R$
关系的闭包: $R^+ = R \cup R^2 \cup R^3 \cup \cdots$
关系的克林包: $R^* = R^0 \cup R^+$

1.5 语言

符号:

  • $\Sigma$ 表示字母表, 通常是有限的
  • $\varepsilon$ 代表空串
  • $\varnothing$ 代表空字符串
  • $a, b, ...$ 代表单个字符
  • $\alpha, \beta, ...$ 代表字符串
  • $A, B, ...$ 代表字符集合
  • $A^n$ 代表集合 $A$ 的 $n$ 次连接
  • $A^*$ 代表 $A$ 上所有字符串的集合

示例:

  • $\alpha = a_1 a_2 a_3 ... a_n$
  • $\beta = b_1 b_2 b_3 ... b_n$
  • $A={a_1, a_2, \cdots, a_n}$
  • $B={b_1, b_2, \cdots, b_n}$
  • $A^0={\varepsilon}, A^2=AA, A^3=AA^2, \cdots, A^n=AA^{n-1}$

若 $\alpha \in A^$, 也称 $\alpha$ 是 $A$ 上的串.
$\Sigma$ 是字母表, $\Sigma^$ 的任意子集 $L$ 称为字母表 $\Sigma$ 上的一个语言.

1.7 形式语言与自动机的发展

Chomsky 形式语言理论
文法与自动机的对应关系

方法类型 文法名称 对应自动机
0 PSG 短语结构方法(无限制文法) 图灵机
1 CSG 上下文有关文法 线性有界自动机
2 CFG 上下文无关文法 下推自动机
3 RLG 右线性文法(正则文法) 有限状态自动机

Backus-Naur Form (BNF) 巴科斯-诺尔范式

第2章 形式语言简介

2.1 例子语言

例子语言用于描述语言中句子形式的规则. 3种常用文法: 自然语言, BNF, 产生式.
例:

  1. 匹配括号:
    1.1. $S \rightarrow ()$
    1.2. $S \rightarrow SS$
    1.3. $S \rightarrow (S)$
  2. 代数式运算:
    2.1. $E \rightarrow E+T | E-T | T$
    2.2. $T \rightarrow T*F | T/F | T%F | A$
    2.3. $A \rightarrow F\mbox{^}A | F$
    2.4. $F \rightarrow (E) | I$
    2.5. $I \rightarrow L | IL | ID$
    2.6. $L \rightarrow a\mbox{~}z$
    2.7. $D \rightarrow 0\mbox{~}9$

2.2 文法和语言的关系

由 $G=(\Sigma, V, S, P)$ 可以定义一种文法, 其中

  • $\Sigma$ 表示所有终结符集合, 又称字母表, 包括基本运算符
  • $V$ 表示所有非终结符集合
  • $S$ 用于开始文法的特殊非终结符
  • $P$ 是 $(\alpha, \beta)$ 的集合, 其中 $\alpha \in (\Sigma \cup V), \beta \in (\Sigma \cup V)^*, \alpha \rightarrow \beta$ 即产生式

2.3 Chomsky 对文法和语言的分类

由 $G=(\Sigma, V, S, P)$ 定义的文法, 称为 0 型文法, 又称短语结构文法 $(PSG)$.
在此基础上又定义有:

  1. 上下文有关文法(CSG): $\forall (\alpha, \beta) \in P, |\alpha| \leqslant |\beta|$
  2. 上下文无关文法(CFG): $\forall (\alpha, \beta) \in P, |\alpha| \leqslant |\beta| 且 \alpha \in V$
  3. 右线性文法(RLG): $\forall (\alpha, \beta) \in P, \alpha \rightarrow \beta 具有 A \rightarrow \omega 或 A \rightarrow \omega B$ 形式, 其中 $\omega \in \Sigma$.
添加新评论