Course Syllabus

Course Information：

Year-Semester Course Number Course Name Phase Credits Hours Required/Elective Instructor Class Student NO. Withdraw Note

Fall Semester
Year 2025 349986 Formal Languages 1 3.0 3 ★ LIN,Jyun-Ao GCSIE
IEECSG
MSIS 9 0 Jointly offered by Computer Science department and Information Security.

Year-Semester	Course Number	Course Name	Phase	Credits	Hours	Required/Elective	Instructor	Class	Student NO.	Withdraw	Note
Fall Semester Year 2025	349986	Formal Languages	1	3.0	3	★	LIN,Jyun-Ao	GCSIE IEECSG MSIS	9	0	Jointly offered by Computer Science department and Information Security.

Course Plan：

Instructor LIN,Jyun-Ao　Office Hours

Email jalin@ntut.edu.tw

Last Updated 2025-06-19 11:06:01

Course Objective 本課程將涵蓋電腦科學的理論基礎。其內容包含自動機理論，電腦語言學，以及計算形式等。電腦相關的基本數學也將涵蓋在課程範圍之中。包括集合論，基本關係及及操作，以及理論證明工具與技術。課程大綱:基礎理論介紹，有限狀態自動機 / 一般敘述語法，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.

Course Schedule 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

Evaluation and grading policy Assignment 50% Mid-term 20% Final 30%

Materials All right reserved. Do not reproduce without permission.

Foreign-language textbooks:No
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” Other supplementary resources: 3. Alexandra Silva, "Kleene Coalgebra", Ph.D. thesis 4. Javier Esparza and Michael Blondin, "Automata Theory -- An Algorithmic Approach", https://michaelblondin.com/automata/ 5. C. Baier, J.-P. Katoen, "Principal of Model Checking"

The access to curricular consultation Email: jalin@ntut.edu.tw

The course corresponds to the SDGs SDG4：優質教育（Quality Education）

Does the course incorporate AI AI2：鼓勵學生使用生成式AI工具（Encourage students to use generative AI tools）

Note
Course Website: TBA

Instructor	LIN,Jyun-Ao　Office Hours
Email	jalin@ntut.edu.tw
Last Updated	2025-06-19 11:06:01
Course Objective	本課程將涵蓋電腦科學的理論基礎。其內容包含自動機理論，電腦語言學，以及計算形式等。電腦相關的基本數學也將涵蓋在課程範圍之中。包括集合論，基本關係及及操作，以及理論證明工具與技術。課程大綱:基礎理論介紹，有限狀態自動機 / 一般敘述語法，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.
Course Schedule	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
Evaluation and grading policy	Assignment 50% Mid-term 20% Final 30%
Materials	All right reserved. Do not reproduce without permission. Foreign-language textbooks:No 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” Other supplementary resources: 3. Alexandra Silva, "Kleene Coalgebra", Ph.D. thesis 4. Javier Esparza and Michael Blondin, "Automata Theory -- An Algorithmic Approach", https://michaelblondin.com/automata/ 5. C. Baier, J.-P. Katoen, "Principal of Model Checking"
The access to curricular consultation	Email: jalin@ntut.edu.tw
The course corresponds to the SDGs	SDG4：優質教育（Quality Education）
Does the course incorporate AI	AI2：鼓勵學生使用生成式AI工具（Encourage students to use generative AI tools）
Note	Course Website: TBA