Automata theory and formal languages
何为“计算”，如何定义“计算”？这一问题直到1936年才在图灵的论文中被揭示。本课程将溯源计算模型的基本理论，介绍自动机理论和形式语言及其应用，内容涵盖有限自动机、下推自动机、图灵机、正则语言、上下文无关语法等核心概念，同时将涉及无穷语言自动机等进阶主题。
What is “computation”? How can we define it? The answer was not clear until Turing’s paper in 1936. This course will trace the fundamental theories of computational models, introducing automata theory, formal languages and their applications. The content will cover core concepts such as finite automata, pushdown automata, Turing machines, regular languages, and context-free grammars, as well as advanced topics like automata on $\omega$-languages.
What is “computation”? How can we define it? The answer was not clear until Turing’s paper in 1936. This course will trace the fundamental theories of computational models, introducing automata theory, formal languages and their applications. The content will cover core concepts such as finite automata, pushdown automata, Turing machines, regular languages, and context-free grammars, as well as advanced topics like automata on $\omega$-languages.
Lecturer
Date
25th March ~ 13th June, 2025
Location
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| Tuesday,Thursday | 09:50 - 11:25 | A3-2a-302 | ZOOM 14 | 712 322 9571 | BIMSA |
Syllabus
1. 有限自动机、正则表达式与正则语言 (Finite automata, regular expression and regular languages)
2. 下推自动机、可视下推自动机、上下文无关语法与上下文无关语言 (pushdown automata, visibly pushdown automata, context-free grammar and context-free languages)
3. 线性有界自动机，上下文有关语法与上下文有关语言 (Linear-bounded automata, context-sensitive grammar, context-sensitive languages)
4. 图灵机与递归可枚举 (Turing machines and recursively enumerable languages)
5. 概率自动机与随机语言 (probabilistic automata and stochastic languages)
6. 无穷语言自动机 (automata on $\omega$-languages)
2. 下推自动机、可视下推自动机、上下文无关语法与上下文无关语言 (pushdown automata, visibly pushdown automata, context-free grammar and context-free languages)
3. 线性有界自动机，上下文有关语法与上下文有关语言 (Linear-bounded automata, context-sensitive grammar, context-sensitive languages)
4. 图灵机与递归可枚举 (Turing machines and recursively enumerable languages)
5. 概率自动机与随机语言 (probabilistic automata and stochastic languages)
6. 无穷语言自动机 (automata on $\omega$-languages)
Reference
[1] Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to automata theory, languages, and computation (3rd ed.). Addison-Wesley. (自动机理论经典教材)
[2] Sipser, M. (2012). Introduction to the theory of computation (3rd ed.). Cengage Learning.（计算理论入门）
[3] Perrin, D., & Pin, J.-É. (2004). Infinite words: Automata, semigroups, logic and games. Academic Press. (自动机与逻辑的进阶教材）
[4] Gr\"{a}del, E., Thomas, W., & Wilke, T. (Eds.). (2002). Automata, logics, and infinite games: A guide to current research (Lecture Notes in Computer Science, Vol. 2500). Springer.（无穷语言自动机、逻辑与博弈的研究报告）
[2] Sipser, M. (2012). Introduction to the theory of computation (3rd ed.). Cengage Learning.（计算理论入门）
[3] Perrin, D., & Pin, J.-É. (2004). Infinite words: Automata, semigroups, logic and games. Academic Press. (自动机与逻辑的进阶教材）
[4] Gr\"{a}del, E., Thomas, W., & Wilke, T. (Eds.). (2002). Automata, logics, and infinite games: A guide to current research (Lecture Notes in Computer Science, Vol. 2500). Springer.（无穷语言自动机、逻辑与博弈的研究报告）
Audience
Advanced Undergraduate
, Graduate
Video Public
No
Notes Public
No
Language
Chinese
, English