形式语言与自动机

研究生课程教学大纲、教学周历

课程序号：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

三、教学周历：