正規語言概論
Introduction to Formal Language
| 節 | 週二 |
|---|---|
3 10:10–11:00 | 正規語言概論 EC122（光復） 2 節連堂 |
4 11:10–12:00 |
* 根據陽明交大上課時間表所列
The goal of this course is to introduce the theoretical framework of computation and foundations of computer science. Regular sets and context-free languages are used everywhere in the design of modern software. Finite automata and pushdown automata are conceptual machines that can process these languages. Defining Turing machines leads us further into the realm of computation theory and provides us a theoretical platform on which we can observe, discuss, and understand the behavior, capability, and limitation of computers. Decidability and tractability are covered in the course as well.
Discrete Mathematics
無備註
Course format: Lectures and/or student discussion.
※ Manual course add is unavailable for this course. 本課程不開放手動加選。 Three (3) examinations: Two (2) mid-terms; One (1) final. Grading policy: Mid-term #1: 30% Mid-term #2: 30% Final: 40% Class attendance: 2.5% per Roll Call (if any) Total: 100% + 2.5% x Number of Roll Call (if any)
Introduction
- 講授：
- 2
Regular Languages
Finite automata, regular expressions, pumping lemma, Myhill-Nerode theorem, etc.
- 講授：
- 8
Context-free Languages
Context-free grammars, properties of CFLs, pumping lemma, Ogden's lemma, CYK algorithm, etc.
- 講授：
- 8
Computational Complexity
Turing machines, decidability, reducibility, time complexity, NP-completeness, etc.
- 講授：
- 18
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction, Finite Automata, Regular Expressions & Languages, and Pushdown Automata, Context-free Grammars & Languages 2026-02-24(二) |
| 第 2 週 | 2026-03-03(二) |
| 第 3 週 | 2026-03-10(二) |
| 第 4 週 | 2026-03-17(二) |
| 第 5 週 | 2026-03-24(二) |
| 第 6 週 | 2026-03-31(二) |
| 第 7 週 | 2026-04-07(二) |
| 第 8 週 | Mid-term Examination #1 2026-04-14(二) |
| 第 9 週 | Turing Machines, Decidability, & Reducibility 2026-04-21(二) |
| 第 10 週 | 2026-04-28(二) |
| 第 11 週 | 2026-05-05(二) |
| 第 12 週 | Mid-term Examination #2 2026-05-12(二) |
| 第 13 週 | Time Complexity, P, NP, & NP-Completeness 2026-05-19(二) |
| 第 14 週 | 2026-05-26(二) |
| 第 15 週 | 2026-06-02(二) |
| 第 16 週 | Final Examination 2026-06-09(二) |
[Required] Introduction to the Theory of Computation (2nd or 3rd Edition), Michael Sipser, Thomson Course Technology. Introduction to Automata Theory, Languages, and Computation (3rd Edition), John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Addison-Wesley. ISBN: 0321476174 (Softback). Problem Solving in Automata, Languages, and Complexity, Ding-Zhu Du, and Ker-I Ko, Wiley-Interscience. ISBN: 0471439606 (Hardback), 0471224642 (Electronic). [Reference, downloadable in the NCTU campus]. An Introduction to Formal Languages and Automata (3rd Edition), Peter Linz, Jones and Bartlett Publishers. ISBN: 0763714224 (Hardback). ※請修課同學尊重智慧財產權﹗勿隨意過度影印教科書或使用未經授權之著作權與電腦軟體等。
- 地點
- EC711
- 時間
- M5 (by appointment only)
- 聯絡方式
- 校內分機 31446