形式語言與自動機

研究生課程教學大綱、教學周曆

課程序号：S00903                                    院（系）：計算機系

一、教學目标和要求：

形式語言與自動機理論是計算機科學理論最重要的組成部分。教學目标是，讓學生深刻理解“計算”的本質含義。要求學生在掌握各種計算模型的基礎上，具有發展新模型的能力，以及把計算模型和實際應用（例如詞法分析）相結合的能力。

二、教學大綱（含章節目錄）：

1 Automata：TheMethods and Madness

  ●Formal Proof

  ●Forms of Proof

 ●Inductive Proof

  ●Concepts of Automata

2 FiniteAutomata

 ●Finite Automata

 ●DFA

 ●NFA

 ●Text Search

 ●Epsilon-Transitions

3 RegularExpressions and Languages

 ●Regular Expressions

 ●FA and RE

 ●Application of RE

 ●Algebraic Laws for RE

4 Properties of Regular Languages

 ●Closure Properties of RL

 ●Decision Properties of RL

5Context-Free Grammars and Languages

 ●CFGs

 ●Parse Trees

 ●Application of CFGs

6Pushdown Automata

 ●Definition of PDA

 ●The Languages of a PDA

 ●Equivalence of PDA’s and CFG’s

7 Properties of Context-FreeLanguages

 ●Normal Forms for CFG

 ●Closure of CFL’s

 ●Decision Properties of CFL’s

8 Introduction to Turing Machines

 ●The Turing Machine

 ●Programming Techniques for TuringMachine

 ●Extensions to the Basic Turing Machine

 ●Restricted Turing Machine

 ●Turing Machines and Computers

9 Undecidability

 ●Not Recursively Enumerable

 ●UndecidableProblems About Turing Machines

10Intractable Problems

11Additional Classes of Problems

三、教學周曆：