你的进度
0/ 27 节已标记完成
下一节: 可区分性与最小确定型自动机
完成记录保存在此浏览器中。
这门课在网上
CSCI3130 笔记里的内容
数字只算这门课 27 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。
在网上定理卡 77 · 定义 61 · 反例 34 · 概念视角 13 · 证明透视 33
第 1 章 · 5 节
正则语言
正则语言
- 1.1
可区分性与最小确定型自动机
由剩余语言构造最小 DFA,并通过划分细化来计算它。
- 1.2
有限自动机、正则表达式与泵引理
定义 DFA、NFA 与正则表达式,证明子集构造、Thompson 构造与状态消去构造,并证明泵引理与基于可区分性的状态数下界。
- 1.3
确定有限自动机的判定问题
利用有限图搜索判定空性、等价性与无穷性。
- 1.4
正则语言的泵引理
利用有限状态的重复与正确的量词顺序证明语言非正则。
- 1.5
同态与正则语言
为同态的正像与逆像构造有限自动机。
第 2 章 · 9 节
上下文无关语言
上下文无关语言
- 2.1
下推自动机:终结状态接受与空栈接受
在保持语言不变的前提下,在两种非确定性下推自动机的接受约定之间相互转换。
- 2.2
范式与栈计算中隐藏的文法
证明上下文无关范式定理,补全泵引理的二叉树前提,并从任意非确定下推自动机构造文法。
- 2.3
基于动态规划的上下文无关文法成员判定
为乔姆斯基(Chomsky)范式文法推导 CYK 表。
- 2.4
上下文无关文法、栈自动机与泵引理
推导、语法分析树与歧义;括号平衡与 aⁿbⁿ 的文法;用非确定型下推自动机模拟文法;上下文无关语言的泵引理及其局限。
- 2.5
化简上下文无关文法
在保持语言不变的前提下消除空产生式与单位产生式。
- 2.6
将文法转换为乔姆斯基范式
在保持上下文无关语言不变的前提下,分离终结符并将产生式二叉化。
- 2.7
上下文无关语言的泵引理
从语法分析树推导上下文无关泵引理,并正确使用其量词。
- 2.8
上下文无关语言与正则约束
将下推自动机与有限自动机结合,并考察封闭性的局限。
- 2.9
确定性下推自动机与接受方式
追踪一台确定性栈机,并证明空栈接受方式带来的前缀限制。
第 3 章 · 2 节
语法分析
语法分析
- 3.1
LR(0) 项目、移进-归约分析与前瞻
增广文法、LR(0) 项目、闭包与 goto、规范族、ACTION/GOTO 表与冲突,一张完整的分析表与一次完整分析,以及通过 S → a | ab 区分 LR(0) 与 LR(1)。
- 3.2
预测分析与 LL(1) 分析表
利用可空性、FIRST 与 FOLLOW 信息构造预测分析表。
第 4 章 · 1 节
上下文有关语言
上下文有关语言
- 4.1
非收缩文法与线性有界带
非收缩文法与长度引理,aⁿbⁿcⁿ 的完整文法及其不变量证明,线性有界自动机,有界带上接受问题的可判定性,用逆向推导模拟文法,以及标记算法。
第 5 章 · 5 节
可计算性
可计算性
- 5.1
图灵机、可判定性与不可判定性
图灵机格局、通用模拟、识别器与判定器、用交错执行证明补集定理、自接受的对角线证明、归约的正确方向、莱斯定理,以及这些语言类在一条链中的位置。
- 5.2
对角法与停机问题归约
区分识别与判定,并用自引用和有效归约证明不可判定性。
- 5.3
莱斯(Rice)定理与语义性质
将停机问题归约到可识别语言的非平凡性质。
- 5.4
为什么 Post 对应问题不可判定
将接受计算编码为对应序列,并去除强制首块骨牌的条件。
- 5.5
为什么上下文无关文法的普遍性不可判定
利用对应骨牌与确定性栈比较,归约到文法普遍性问题。
第 6 章 · 2 节
自动机例题
自动机例题
- 6.1
有限自动机:状态作为不变量
构造并证明一个追踪奇偶性的确定有限自动机。
- 6.2
非确定性、ε-闭包与子集构造
追踪 NFA 的全部可能状态,处理不消耗输入的转移,并证明由子集组成的 DFA 识别相同语言。
第 7 章 · 1 节
正则约束
结合有限状态条件与上下文无关推导。
- 7.1
正则限制下的上下文无关语言
构造上下文无关语言与正则语言交集的文法,并证明其正确性。
第 8 章 · 1 节
平衡括号与文法歧义
分析树、首次归零分解与歧义。
- 8.1
上下文无关文法:分析树、歧义与平衡括号
证明文法恰好生成平衡括号语言,用首次归零分解消除歧义,并联系语法分析、有限状态的限制与计数。
第 9 章 · 1 节
下推自动机
证明栈不变量和非确定性识别。
- 9.1
下推自动机:栈不变量与非确定性回文
用栈记录未匹配的符号,并证明两个下推自动机识别的语言。