CS4114 形式语言与自动机
目录
| 关于
目录
::
1.
如何使用本系统
»
Chapter 0
Preface
¶
1. 如何使用本系统
Chapter 1
Introduction
¶
1. 关于本课程与本书
1.1. 引言
1.2. 先修要求
1.3. 本书的运作方式
1.4. 我们将要做的事
2. 概述
2.1. 语言、文法与机器
2.2. 语言层次
2.3. 机器的能力
2.4. 应用：编译器
2.4.1. 编译器的各个阶段
2.5. 一些令人费解的想法
3. 形式语言入门
3.1. 引言
3.2. 语言
3.3. 文法
3.4. 文法练习
3.5. 自动机
4. 文法练习
4.1. 文法练习
Chapter 2
Mathematical Background
¶
1. 集合记号
1.1. 集合入门
1.2. 集合的常用记号
2. 集合记号
2.1. 集合入门
3. 关系
3.1. 关系
3.2. 等价类与偏序
4. 数学证明技巧
4.1. 数学证明技巧
4.1.1. 直接证明
4.1.2. 反证法
4.1.3. 数学归纳证明
5. 数学证明技巧
5.1. 数学证明类型
5.2. 数学归纳法
5.3. 归纳证明示例
Chapter 3
Finite Acceptors
¶
1. DFA：确定的有穷接受器
1.1. DFA 简介
1.2. 一些示例
1.3. 进阶概念
1.4. DFA 的局限
2. DFA 练习 1
2.1. DFA 练习
3. DFA 练习 2
3.1. DFA 练习
4. DFA 练习 3
4.1. DFA 练习
5. NFA：非确定性有限自动机
5.1. 非确定性有限自动机
5.2. NFA 与 DFA：哪个更强大？
5.3. NFA 到 DFA 转换示例
5.4. 结论
6. NFA 练习
6.1. NFA 转 DFA
6.2. 创建 NFA
7. 更多 NFA 练习
7.1. NFA 转 DFA
7.2. 创建 NFA
8. 最小化 DFA 的状态数
8.1. 最小化 DFA 的状态数
8.2. 最小化示例 1
8.3. 最小化示例 2
8.4. 可判定性
9. DFA 最小化练习
9.1. DFA 最小化练习
Chapter 4
Regular Languages
¶
1. 正则表达式
1.1. 正则表达式的定义与示例
2. 正则表达式练习
2.1. 练习 1
2.2. 练习 2
2.3. 练习 3
2.4. 练习 4
3. 更多正则表达式练习
3.1. 练习 1
3.2. 练习 2
3.3. 练习 3
3.4. 练习 4
4. 正则表达式的能力
4.1. 每个正则表达式都有等价的 NFA
4.2. 将正则表达式转换为 NFA
4.3. 正则表达式到最小化 DFA 的示例
4.4. 将 NFA 转换为正则表达式
4.5. 小结
5. 正则文法
5.1. 正则文法导论
5.2. 将正则文法转换为 NFA
5.3. 将 NFA 转换为正则文法
5.4. 左线性与右线性文法之间的转换
5.5. 正则表达式与正则文法
5.6. 小结
6. 正则文法
6.1. 正则文法导论
6.2. 将正则文法转换为 NFA
6.3. 将 NFA 转换为正则文法
6.4. 左线性与右线性文法之间的转换
6.5. 小结
7. 正则文法练习
7.1. 正则文法练习
8. 更多正则文法练习
8.1. 更多正则文法练习
9. 正则语言的闭包性质
9.1. 闭包概念
9.2. 正则语言的闭包性质——基本运算
9.3. 右商
9.4. 同态
9.5. 关于正则语言的一些可判定问题
9.6. 小结：如何证明一个语言是正则语言？
10. 性质
10.1. 引言
10.2. 性质与证明：问题 1
10.3. 性质与证明——问题 2
Chapter 5
Identifying Non-regular Languages
¶
1. 识别非正则语言
1.1. 识别非正则语言
1.2. 泵的概念
1.3. 泵引理
1.4. 一些泵引理示例
1.5. 泵引理对抗博弈
1.6. 使用闭包性质证明 L 非正则
1.7. 值得思考的问题
Chapter 6
Context-Free Grammars and Languages
¶
1. 上下文无关文法（一）
1.1. 上下文无关语言
1.2. 串推导
1.3. 推导树
1.4. 推导树示例
1.5. 练习题 1
1.6. 成员问题
1.7. 练习题 2
2. 上下文无关文法（二）
2.1. 二义性
2.1.1. 有歧义文法（1）
2.1.2. 有歧义文法（2）
2.1.3. 有歧义文法（3）
2.1.4. 有歧义文法（4）
2.2. 优先级练习
2.3. 无歧义文法的分析树示例
2.3.1. 结合性
2.3.2. 优先级与结合性
2.4. 为什么是上下文无关？
3. 编写编译器
3.1. 巴科斯-诺尔范式
3.2. 扩展 BNF
4. CFG 练习
4.1. CFG 练习
5. 文法的变换
5.1. 文法的变换
5.2. 删除无用产生式
5.3. 删除 Lambda 产生式
5.4. 删除单元产生式
5.5. 乔姆斯基范式（CNF）
5.6. 格雷巴赫范式（GNF）
6. 文法变换练习
6.1. 文法变换练习
Chapter 7
Pushdown Automata
¶
1. 下推自动机
1.1. PDA：下推自动机
1.2. PDA 的转移类型
1.3. PDA 接受模型——最终状态接受
1.4. PDA 接受模型——空栈接受
1.5. 接受定义的等价性
1.6. 思考题
2. PDA 练习
2.1. PDA 练习
3. 下推自动机与上下文无关语言
3.1. 下推自动机与上下文无关语言
3.2. 将 CFG 转换为 NPDA
3.3. 将 NPDA 转换为 CFG
4. 确定的下推自动机
4.1. 确定的下推自动机
4.2. 证明存在不是 DCFL 的 CFL
4.3. 确定的上下文无关语言的文法
Chapter 8
Properties of Context-free Languages
¶
1. 证明一个语言不是上下文无关的
1.1. 引言
1.2. 上下文无关语言的封闭性质
1.3. 上下文无关语言的泵引理
1.4. 使用上下文无关文法泵引理证明一个语言不是上下文无关语言：示例 1
1.5. 泵引理示例 2
1.6. 泵引理示例
1.7. 4 泵引理示例
Chapter 9
Turing Machines
¶
1. 图灵机导论
1.1. 通用计算模型
1.2. 图灵机
1.3. 解释图灵机
1.4. 图灵可判定与图灵可接受语言
2. 图灵机：进阶专题
2.1. 构造更复杂的机器
2.2. 无限制文法和上下文相关文法
2.3. 简单算术……以及更多
2.4. 图灵论题与算法
2.5. 图灵机扩展
3. 图灵机练习
3.1. 练习 1
3.2. 练习 2
3.3. 练习 3
3.4. 练习 4
3.5. 练习 5
3.6. 练习 6
3.7. 练习 7
3.8. 练习 8
3.9. 练习 9
4. 图灵机练习
4.1. 练习 1
4.2. 练习 2
4.3. 练习 3
4.4. 练习 4
4.5. 练习 5
Chapter 10
Limits to Computing
¶
1. 计算的极限
1.1. 计算的极限
2. 归约
2.1. 归约
2.1.1. 归约与下界求解
2.2. 归约示例
2.3. 界定理
3. NP 完全性
3.1. 困难问题
3.2. 证明一个问题是 NP 完全的
3.3. 应对 NP 完全问题
4. 不可解问题
4.1. 不可解问题
4.2. 停机问题不可解
Chapter 11
Parsing
¶
1. 分析引言
1.1. 引言
1.1.1. 自顶向下分析器（Top-down Parser）：
1.1.2. 函数 FIRST
1.1.3. 函数 FOLLOW
2. LL 分析
2.1. LL 分析
2.1.1. LL(k) 分析器
2.1.2. LL 分析过程
2.1.3. 将 CFG 转换为 NPDA
2.1.4. LL 分析表：二维数组
2.1.5. 通用的分析例程
2.1.6. 构造 LL 分析表 LL[rows,cols]
3. LR 分析
3.1. LR 分析
3.1.1. LR(k) 分析器
3.1.2. LR 分析过程
3.1.3. LR 分析动作
3.1.4. LR(1) 分析表
4. CYK 分析
4.1. CYK 分析
4.1.1. CYK 分析算法
4.1.2. 算法
5. 编译器的结构
5.1. 什么是编译器？
5.1.1. 翻译器
5.2. 语言处理系统
5.2.1. 编译器
5.3. 通用编译器总览
5.4. 编译的阶段
5.4.1. 词法分析（扫描器）
5.4.2. 语法分析（Parsing）
5.4.3. 1.3.3 中间代码生成器
5.4.4. 1.3.4 中间代码生成
5.4.5. 代码生成
5.4.6. 符号表
5.4.7. 错误处理（Error Handler）
Chapter 12
Appendix
¶
1. 术语表
TODO List
索引
搜索页面
隐私 |
| 许可协议
目录
::
1.
如何使用本系统
»
小结*:
操作系统*:
Windows
Mac OS
Linux
iOS
Android
Other
浏览器*:
Chrome
Safari
Internet Explorer
Opera
Other
描述*:
附加截图（可选）:
