“形式化语言与自动机理论”学习笔记
基础知识
集合
幂集 \(2^S=\text{power} (S)=\{x|x\subseteq S\}\) ，表示的是集合 \(S\) 的所有子集（包括空集）所组成的集合。
元祖
序列是有序排列的一组元素。
元祖是有限个数的序列。
笛卡尔积
\(A\times B=\{(x,y)|x\in A\; and \; y\in B\}\) 。
关系
- 定义域表示为 \(\text{dom}(R)\)
- 值域表示为 \(\text{ran}(R)\)
- 二元关系 \((x,y)\in R\) 可以写成 \(xRy\)
- 逆关系 \(R^{-1}=\{(y,x)|(x,y)\in R\}\)
偏序关系
满足 自反、反对称、传递 三个性质的关系，称为偏序关系。
集合 \(S\) 和偏序关系 \(R\) 构成一个偏序集 \((S,R)\)
常见的偏序关系：
- \((\mathbb{N},\le )\)
- \((2^{S},\subseteq )\)
等价关系
满足 自反、对称、传递 三个性质的关系，称为等价关系。
等价类：由等价关系确定的一组集合，每个集合中的任意元素都相互等价。
等价关系的秩：等价类的个数。
函数
函数是一个特殊的关系，从定义域到值域的一个关系。
函数的表示方法 \(f:X\rightarrow Y\)
- 全函数 \(\{x|(x,y)\in f\}=X\)（覆盖了所有的定义域）
- 偏函数 \(\{x|(x,y)\in f\}\subseteq X\)（不需要覆盖了所有的定义域），全函数是一个特殊的偏函数
- 满射函数 \(\{y|(x,y)\in f\}= Y\) （覆盖了所有的值域）
- 单射函数 \(\forall x,y\in X,x\neq y\Rightarrow f(x)\neq f(y)\) （不同的元素对应的输出不同）
- 双射函数是满足单射和满射的函数
- 双射函数的定义域与值域的大小相同
语言
- 字母表是语言中出现的原子符号，通常用 \(\sum\) 表示。
- 字符串是由字母表中的元素构成的序列。
- 语言是一系列特殊字符串的集合 \(L\subseteq \sum ^{*}\)。
图
一个图可以表示为一个二元组 \((S,T)\)
- \(S\) 是节点的集合
- \(T\subseteq S\times S\) 是节点与节点的连接关系
无向图中的关系 \(T\) 是对称的
带标签的图
图的节点和边上都可以带上特定的标签
带标签的图可以表示为一个四元组 \((S,T,D,L)\)
- \(D\) 是标签的集合
- \(L:S \cup T\rightarrow D\) ，表示标签所在的位置
路径：是由节点组成的序列，每两个相邻的节点都由边相连
强连通图：图中的任意两个节点之间都存在一条路径
迁移系统
迁移系统包括 状态、动作、变迁关系 。
推理
演绎推理
- 公理：不需要证明的公式的模版
- 几个常见的推理：
- MP规则 \(\frac{p,p\Rightarrow q}{q}\)
- 矛盾规则 \(\frac{p\Rightarrow q,\neg q}{\neg p}\)
- 传递规则 \(\frac{p\Rightarrow q,q\Rightarrow r}{p\Rightarrow r}\)
- 公理系统由一个集合的公理构成，可以由推理规则导出一系列定理
定理证明
从下往上读证明规则 \(\frac{A}{C}\) ：若要证明 \(C\) ，只需证明 \(A\)
\(A\) 和 \(C\) 是相继式的集合：
- \(H\vdash G\)
- \(H\) 称为前件
- \(G\) 称为后件
归纳证明
已知一类事物的部分对象具有性质，以此来证明这类事物的所有对象都具有这个性质。
- 归纳推理是从特殊到一般的推理。
- 归纳推理的前提是结论的必要条件。
数学归纳法
证明一个关于自然数 \(n\) 的命题 \(P(n)\)
分为两个步骤：
- 基础步：证明 \(P(0),P(1)\) ；
- 归纳步：假设 \(P(n)\) 成立，证明 \(P(n+1)\) 成立。
结构归纳法
对于一类递归定义的对象 \(o\)，证明性质 \(P(o)\) 对所有的 \(o\) 都成立。
分为两个步骤：
- 基础步：证明集合中最基本的元素性质 \(P\);
- 归纳步：证明由满足性质 \(P\) 的元素按照递归规则构造出的新元素也满足性质 \(P\) 。
形式语言
形式语言 \(L=(\sum ,G)\)
- \(\sum\) 表示字母表（集合）
- \(G\) 表示语法
语法 \(G=(V,T,P,S)\)
- \(V\) 代表变量，非终止符号
- \(T\) 终止符号
- \(P\) 关系 \(\alpha \rightarrow \beta (\alpha \in (V\cup T)^{+},\beta in (V\cup T)^{*})\)
- \(S\) 起始符号
文法
文法的分类：
- \(0\) 型文法：由文法结构定义的文法，也叫递归可枚举文法
- \(1\) 型文法（上下文相关文法）： \(\alpha A \beta \rightarrow \alpha \gamma \beta \) ，其中 \(A\) 应该是非终止符
- \(2\) 型文法（上下文无关文法）：\(A\rightarrow \beta \) ，其中 \(A\) 应该是非终止符
- \(3\) 型文法（正则）： \(A\rightarrow \sigma B|\sigma\)，其中 \(\sigma\) 是终止符
- \(3\) 型 \(\subset 2\) 型 \(\subset 1\) 型 \(\subset 0\) 型
文法类型的等价性：
- 长度递增文法 \(\mathbb{G}_{inc}\) ，产生式右边字串长度大于左边
- 长度递增文法与上下文有关文法等价
自动机
- 可以参见 “《计算理论基础》学习笔记”自动机部分
下推自动机
下推自动机，Pushdown Automata ，简称 PDA 。
可以看成是 \(\varepsilon-\)NFA 和一个 stack 。
一个 PDA 由七元组确定 \(P=(Q,\sum ,\Gamma ,\delta ,q_o,Z_o,F)\)
- \(Q\) 是有限状态集合
- \(\sum\) 是有限输入符号集合
- \(\Gamma\) 是有限的栈符号的集合
- \(\delta: Q\times \sum \times \Gamma \rightarrow 2^{Q\times \Gamma^{*}}\) 是迁移函数
- \(q_o\in Q\) 是初始态
- \(Z_0\in \Gamma\) 是栈的开始符号
- \(F\subseteq Q\) 是终止状态
PDA 的一次迁移的工作
- 消耗一个输入字符
- 迁移到一个新的状态（或者在原来的状态上）
- 把栈顶的符号替换成任意的字符串（可以是空串或者跟原来一样的字符串）
转移标签的格式：a,z/y （读到的字符 a，将 z 替换成 y）
PDA ID 是一个三元组 \((q,w,\alpha)\)
- \(q\) 是当前状态
- \(w\) 是剩余的输入字符串
- \(\alpha\) 是当前栈的状态
状态转移 \((q,aw,z\beta)\vdash (p,w,y\beta)\) ，如果 \((p,y)\in \delta(q,a,z)\)