跳到正文

CSCI3130

形式语言及自动机理论

有限自动机与正则语言、上下文无关文法与下推自动机、语法分析、上下文有关语言、图灵机与不可判定性。

9 章 · 27 节EN · 繁 · 简
我的课程笔记

你的进度

0/ 27 节已标记完成

下一节: 可区分性与最小确定型自动机

完成记录保存在此浏览器中。

这门课在网上

CSCI3130 笔记里的内容

定理卡
77
定义
61
反例
34
概念视角
13
思想史
0
证明透视
33

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 27 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

在网上定理卡 77 · 定义 61 · 反例 34 · 概念视角 13 · 证明透视 33

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 27 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

第 1 章 · 5 节

正则语言

正则语言

定理 16 · 定义 14反例 8视角 1证明透视 6

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 1.1

    可区分性与最小确定型自动机

    由剩余语言构造最小 DFA,并通过划分细化来计算它。

  2. 1.2

    有限自动机、正则表达式与泵引理

    定义 DFA、NFA 与正则表达式,证明子集构造、Thompson 构造与状态消去构造,并证明泵引理与基于可区分性的状态数下界。

  3. 1.3

    确定有限自动机的判定问题

    利用有限图搜索判定空性、等价性与无穷性。

  4. 1.4

    正则语言的泵引理

    利用有限状态的重复与正确的量词顺序证明语言非正则。

  5. 1.5

    同态与正则语言

    为同态的正像与逆像构造有限自动机。

第 2 章 · 9 节

上下文无关语言

上下文无关语言

定理 21 · 定义 13反例 11视角 3证明透视 10

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 2.1

    下推自动机:终结状态接受与空栈接受

    在保持语言不变的前提下,在两种非确定性下推自动机的接受约定之间相互转换。

  2. 2.2

    范式与栈计算中隐藏的文法

    证明上下文无关范式定理,补全泵引理的二叉树前提,并从任意非确定下推自动机构造文法。

  3. 2.3

    基于动态规划的上下文无关文法成员判定

    为乔姆斯基(Chomsky)范式文法推导 CYK 表。

  4. 2.4

    上下文无关文法、栈自动机与泵引理

    推导、语法分析树与歧义;括号平衡与 aⁿbⁿ 的文法;用非确定型下推自动机模拟文法;上下文无关语言的泵引理及其局限。

  5. 2.5

    化简上下文无关文法

    在保持语言不变的前提下消除空产生式与单位产生式。

  6. 2.6

    将文法转换为乔姆斯基范式

    在保持上下文无关语言不变的前提下,分离终结符并将产生式二叉化。

  7. 2.7

    上下文无关语言的泵引理

    从语法分析树推导上下文无关泵引理,并正确使用其量词。

  8. 2.8

    上下文无关语言与正则约束

    将下推自动机与有限自动机结合,并考察封闭性的局限。

  9. 2.9

    确定性下推自动机与接受方式

    追踪一台确定性栈机,并证明空栈接受方式带来的前缀限制。

第 3 章 · 2 节

语法分析

语法分析

定理 6 · 定义 7反例 2视角 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 3.1

    LR(0) 项目、移进-归约分析与前瞻

    增广文法、LR(0) 项目、闭包与 goto、规范族、ACTION/GOTO 表与冲突,一张完整的分析表与一次完整分析,以及通过 S → a | ab 区分 LR(0) 与 LR(1)。

  2. 3.2

    预测分析与 LL(1) 分析表

    利用可空性、FIRST 与 FOLLOW 信息构造预测分析表。

第 4 章 · 1 节

上下文有关语言

上下文有关语言

定理 5 · 定义 3反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 4.1

    非收缩文法与线性有界带

    非收缩文法与长度引理,aⁿbⁿcⁿ 的完整文法及其不变量证明,线性有界自动机,有界带上接受问题的可判定性,用逆向推导模拟文法,以及标记算法。

第 5 章 · 5 节

可计算性

可计算性

定理 15 · 定义 13反例 5视角 2证明透视 7

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 5.1

    图灵机、可判定性与不可判定性

    图灵机格局、通用模拟、识别器与判定器、用交错执行证明补集定理、自接受的对角线证明、归约的正确方向、莱斯定理,以及这些语言类在一条链中的位置。

  2. 5.2

    对角法与停机问题归约

    区分识别与判定,并用自引用和有效归约证明不可判定性。

  3. 5.3

    莱斯(Rice)定理与语义性质

    将停机问题归约到可识别语言的非平凡性质。

  4. 5.4

    为什么 Post 对应问题不可判定

    将接受计算编码为对应序列,并去除强制首块骨牌的条件。

  5. 5.5

    为什么上下文无关文法的普遍性不可判定

    利用对应骨牌与确定性栈比较,归约到文法普遍性问题。

第 6 章 · 2 节

自动机例题

自动机例题

定理 4 · 定义 4反例 3视角 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 6.1

    有限自动机:状态作为不变量

    构造并证明一个追踪奇偶性的确定有限自动机。

  2. 6.2

    非确定性、ε-闭包与子集构造

    追踪 NFA 的全部可能状态,处理不消耗输入的转移,并证明由子集组成的 DFA 识别相同语言。

第 7 章 · 1 节

正则约束

结合有限状态条件与上下文无关推导。

定理 2 · 定义 2反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 7.1

    正则限制下的上下文无关语言

    构造上下文无关语言与正则语言交集的文法,并证明其正确性。

第 8 章 · 1 节

平衡括号与文法歧义

分析树、首次归零分解与歧义。

定理 6 · 定义 3反例 1视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 8.1

    上下文无关文法:分析树、歧义与平衡括号

    证明文法恰好生成平衡括号语言,用首次归零分解消除歧义,并联系语法分析、有限状态的限制与计数。

第 9 章 · 1 节

下推自动机

证明栈不变量和非确定性识别。

定理 2 · 定义 2反例 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 9.1

    下推自动机:栈不变量与非确定性回文

    用栈记录未匹配的符号,并证明两个下推自动机识别的语言。

Vercel 访问统计与公开页面性能测量分别征求同意,均非使用网站的必要条件。

网站功能存储(按需使用)

安全、登录和你选择的偏好会按需使用存储,与可选统计分开处理。

撤回会停止后续统计;需要卸载已加载的统计程序时,页面会刷新。已发送的数据不会因此删除。

查看 Cookie 与存储详情