查詢教學大綱與進度

教學大綱與進度

課程基本資料：

學年期課號課程名稱階段學分時數修教師班級人撤備註

113-1 336152 正規語言 1 3.0 3 ★ 林濬璈資工所
電資外生所
創新資安學位學程 26 1 資工所、資安學程和電資國際班合開

學年期	課號	課程名稱	階段	學分	時數	修	教師	班級	人	撤	備註
113-1	336152	正規語言	1	3.0	3	★	林濬璈	資工所電資外生所創新資安學位學程	26	1	資工所、資安學程和電資國際班合開

教學大綱與進度：

教師姓名林濬璈　教師諮商時間(Office Hours)

Email jalin@ntut.edu.tw

最後更新時間 2024-11-22 10:36:10

課程大綱本課程將涵蓋電腦科學的理論基礎。其內容包含自動機理論，電腦語言學，以及計算形式等。電腦相關的基本數學也將涵蓋在課程範圍之中。包括集合論，基本關係及及操作，以及理論證明工具與技術。課程大綱:基礎理論介紹，有限狀態自動機 / 一般敘述語法，Regular 集合的基本性質，前後文無相關文法， Pushdown 自動機，杜林機（turning machines），Chomsky 層次結構，基本關係及操作，理論證明技術及工具。 This course will look the theoretical foundation in computer science. Automata theory, languages, and computation formalism will be examined in details. Various fundamental computer-related mathematics will also be covered. They include, sets/subsets, basic relations and operations and tools/techniques for proving theorems. Course Outline: Introduction to Theoretical Foundations, Finite Automata / Regular Expression, Properties of Regular Sets, Context-Free Grammars, Pushdown Automata, Turing Machines, The Chomsky Hierarchy (tentative), Basic Relations and Operations, Tools/Techniques for Proving Theorems.

課程進度 1) Regular Languages (4 weeks): Deterministic and non-deterministic finite automata, closure properties, regular expressions, Brzozowski derivatives, the pumping lemma for regular languages, DFA minimization, the Myhill-Nerode theorem. 2) Context-Free Languages (4 weeks): Context-free grammars, normal forms, the pumping lemma for context-free languages, pushdown automata, closure properties. 3) Decidable and Undecidable Languages (5 weeks): Turing machines, the Church-Turing thesis, computability, undecidability, the Halting Problem, reductions, basic complexity classes. 4) Model Checking (3 weeks): Buechi-Automata, Kripke system, Linear Temporal Logic, Conputational Tree Logic, Model Checking Problem, Algorithms for MC. Week 1: Introduction Week 2--4: Finite State Automata & Regular Language Week 5--8: Context-Free Languages & Pushdown Automata Week 9: mid-term Week 10--12: Turing Machine & Complexity Theorem Week 13--16: Model Checking Week 17: Final Project Presentation Week 18: Final Project Presentation

評量方式與標準 Assignment 50% Mid-term 20% Final 30%

使用教材、參考書目或其他 【遵守智慧財產權觀念，請使用正版教科書，不得使用非法影印教科書】

使用外文原文書：否
There is no required textbook for this course. However, lectures are based largely on the following sources—you can consider one of these if you're looking for a reference: 1. Michael Sipser. “Introduction to the Theory of Computation” 2. John Hopcroft and Jeffrey Ullman. “Introduction to Automata Theory, Languages, and Computation”

課程諮詢管道 Email: jalin@ntut.edu.tw

延伸教學與資源

課程對應SDGs指標 SDG3：良好健康和福祉（Good Health and Well-being）
SDG4：優質教育（Quality Education）
SDG5：性別平等（Gender Equality）
SDG9：產業創新與基礎設施（Industry, Innovation and Infrastructure）
SDG10：減少不平等（Reduced Inequalities）

課程是否導入AI

備註
Course Website:
https://carquois42.github.io/formal.html

教師姓名	林濬璈　教師諮商時間(Office Hours)
Email	jalin@ntut.edu.tw
最後更新時間	2024-11-22 10:36:10
課程大綱	本課程將涵蓋電腦科學的理論基礎。其內容包含自動機理論，電腦語言學，以及計算形式等。電腦相關的基本數學也將涵蓋在課程範圍之中。包括集合論，基本關係及及操作，以及理論證明工具與技術。課程大綱:基礎理論介紹，有限狀態自動機 / 一般敘述語法，Regular 集合的基本性質，前後文無相關文法， Pushdown 自動機，杜林機（turning machines），Chomsky 層次結構，基本關係及操作，理論證明技術及工具。 This course will look the theoretical foundation in computer science. Automata theory, languages, and computation formalism will be examined in details. Various fundamental computer-related mathematics will also be covered. They include, sets/subsets, basic relations and operations and tools/techniques for proving theorems. Course Outline: Introduction to Theoretical Foundations, Finite Automata / Regular Expression, Properties of Regular Sets, Context-Free Grammars, Pushdown Automata, Turing Machines, The Chomsky Hierarchy (tentative), Basic Relations and Operations, Tools/Techniques for Proving Theorems.
課程進度	1) Regular Languages (4 weeks): Deterministic and non-deterministic finite automata, closure properties, regular expressions, Brzozowski derivatives, the pumping lemma for regular languages, DFA minimization, the Myhill-Nerode theorem. 2) Context-Free Languages (4 weeks): Context-free grammars, normal forms, the pumping lemma for context-free languages, pushdown automata, closure properties. 3) Decidable and Undecidable Languages (5 weeks): Turing machines, the Church-Turing thesis, computability, undecidability, the Halting Problem, reductions, basic complexity classes. 4) Model Checking (3 weeks): Buechi-Automata, Kripke system, Linear Temporal Logic, Conputational Tree Logic, Model Checking Problem, Algorithms for MC. Week 1: Introduction Week 2--4: Finite State Automata & Regular Language Week 5--8: Context-Free Languages & Pushdown Automata Week 9: mid-term Week 10--12: Turing Machine & Complexity Theorem Week 13--16: Model Checking Week 17: Final Project Presentation Week 18: Final Project Presentation
評量方式與標準	Assignment 50% Mid-term 20% Final 30%
使用教材、參考書目或其他	【遵守智慧財產權觀念，請使用正版教科書，不得使用非法影印教科書】使用外文原文書：否 There is no required textbook for this course. However, lectures are based largely on the following sources—you can consider one of these if you're looking for a reference: 1. Michael Sipser. “Introduction to the Theory of Computation” 2. John Hopcroft and Jeffrey Ullman. “Introduction to Automata Theory, Languages, and Computation”
課程諮詢管道	Email: jalin@ntut.edu.tw
延伸教學與資源
課程對應SDGs指標	SDG3：良好健康和福祉（Good Health and Well-being） SDG4：優質教育（Quality Education） SDG5：性別平等（Gender Equality） SDG9：產業創新與基礎設施（Industry, Innovation and Infrastructure） SDG10：減少不平等（Reduced Inequalities）
課程是否導入AI
備註	Course Website: https://carquois42.github.io/formal.html