“形式化语言与自动机理论”学习笔记


基础知识

集合

幂集 \(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)\)

分为两个步骤:

  1. 基础步:证明 \(P(0),P(1)\) ;
  2. 归纳步:假设 \(P(n)\) 成立,证明 \(P(n+1)\) 成立。

结构归纳法

对于一类递归定义的对象 \(o\),证明性质 \(P(o)\) 对所有的 \(o\) 都成立。

分为两个步骤:

  1. 基础步:证明集合中最基本的元素性质 \(P\);
  2. 归纳步:证明由满足性质 \(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)\)

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 67,589

Categories

Archive

Comments