Introduce the mathematical basics of computer science.

教學目標

Introduction to Automata and Grammar. Introduction to Turing Machine, and how to model the process of computation in Turing. Brief Introduction to Complexity. Study the properties of classes of solvable and unsolvable problems. Solve or prove unsolvable open problems. Determine reducibility and equivalence relations among unsolvable problems. Apply results to various other areas of CS.

課程大綱

week1：Introduction

week2：Mathematical Preliminaries & Languages

week3：Finite Automata and Nondeterministic Finite Automata

week4：Finite Automata and Nondeterministic Finite Automata

week5：Properties of Regular Languages and Regular Expressions

week6：Regular Grammars

week7：Elementary Questions for Reg. Lang. and Pumping Lemma for Regular Languages

week8：Context-Free Languages

week9：Simplifications of Context-Free

week10：Grammars and Normal Forms

week11：Pushdown Automata and Context-Free Lang

week12：Pushdown Automata and Context-Free Lang

week13：Pumping Lemma for Context-Free Languages

week14：Turing Machines

week15：Universal Turing Machines

week16：Recursive and Recursively Enumerable Languages

week17：Chomsky's Hierarchy and Decidability

week18：The Post-Correspondence Problem and Time Complexity; NP-completeness