《形式语言与自动机是计算机科学的基础理论之一》由会员分享，可在线阅读，更多相关《形式语言与自动机是计算机科学的基础理论之一（90页珍藏版）》请在金锄头文库上搜索。
1、2018/9/10,中国石油大学（北京） 董华松,1,INTRODUCTION TO COMPUTATION THEORY,2018/9/10,中国石油大学（北京） 董华松,2,Why study this course?,形式语言与自动机是计算机科学的基础理论之一，是计算机学科的专业基础课。 在人工智能、电信领域等有广泛的应用。 通过一些定理的证明和应用，对大家进行思维训练，从而为今后学习通信软件，协议工程，编译技术，人工智能等内容提供理论基础。,2018/9/10,中国石油大学（北京） 董华松,3,COURSE SUBJECT,This course is an introduction
2、to the Theory of Computation. (有限状态自动机，正规语言，正规表达式, 上下文无关文法，上下文无关语言，下推自动机, 图灵机，计算问题分类) But what does Theory of Computation mean?,2018/9/10,中国石油大学（北京） 董华松,4,THEORY,Study of abstractions of reality. Irrelevant complications are dropped in order to isolate important concepts. Studying the “theory of sub
3、ject X“ means that simplified versions of X are analyzed from various perspectives. So the objects being analyzed in a theory are supposed to be simple. Doesnt mean that the subject is easy!,2018/9/10,中国石油大学（北京） 董华松,5,COMPUTATION,Theres more than one kind of computation. Our general approach is to s
4、tart with very simple, deliberately restricted models of computers. Goal is to understand them and then to proceed more complex models. We will study three models: Automata, Grammars, and Turing Machines We work with each model in order to see what can be done with it. Well reason about the models,
5、e.g. to prove the relationship between them.,2018/9/10,中国石油大学（北京） 董华松,6,WHY STUDY THEORY？,Theory gives exposure to ideas that permeate Computer Science: Logic, sets, recursion, automata, grammars. Familiar with these concepts will make you a Better computer scientist. Theory gives us mathematical(he
6、nce precise) descriptions of computational phenomena. This allow us to use mathematics to solve problems arising from computer It gives training in argumentation, which is generally useful thing.,A questions commonly posed by practised minded students! Here is some answers.,2018/9/10,中国石油大学（北京） 董华松,
7、7,it is required if you are interested in a research career in Computer Science. A theory course distinguishes you from someone who has picked up programming at a “job factory“ technique school. Theory gives exposure to some of the absolute highpoints of human thought. Theory gives a nice setting fo
8、r honing your problem solving skills. You will get much practice in solving problems in this course.,2018/9/10,中国石油大学（北京） 董华松,8,TEXTBOOK,2018/9/10,中国石油大学（北京） 董华松,9,AUTHORS,2018/9/10,中国石油大学（北京） 董华松,10,SYLLABI,Preliminaries Automata(Finite Automata, Regular expressions, Regular Grammars, Properties of
9、 Regular language) Grammars(Context-free Grammars and languages, Pushdown Automata, Properties of Context-free languages) Turing Machines(Introduction to Turing Machines, Computability, Complexity),2018/9/10,中国石油大学（北京） 董华松,11,PREREQUISITES,You will need a good working knowledge of the material for t
10、his course. it is highly recommended that you brush up on the following topics: sets, relations, functions, logic, proof techniques, graph theory, counting techniques, permutations and combinations, etc.,2018/9/10,中国石油大学（北京） 董华松,12,EXAMINATION,Every students is required to submit two tractates (30%
11、of total marks) for developing the course. The final examination (70% of total marks) will be a two-hour examination at he end of the term. To pass the course you must have a passing mark on the final examination and the tractates.,2018/9/10,中国石油大学（北京） 董华松,13,Session 1,Inductive ProofsThe Central Co
12、ncepts of Automata Theory,2018/9/10,中国石油大学（北京） 董华松,14,Inductive Proofs,2018/9/10,中国石油大学（北京） 董华松,15,Induction is an extremely important proof technique that can be used to prove assertions, it is used extensively to prove results about the a large variety of recursively defined objects. Many of the m
13、ost familiar inductive proofs deal with integers, but in automate theory, we also need inductive proofs about recursively defined concept as expressions of various sorts.,2018/9/10,中国石油大学（北京） 董华松,16,Induction on Integers,In order to prove a statement S (n), about an integer n. One common approach is
14、 to prove two things: 1. The basis step, where we show S (i) for a particular integer i. (Usually, i = 0 or i= 1.) 2. The inductive step, where we assume n i, where i is the basis integer, and we show that “if S (n) then S (n + 1).“ Intuitively, these two parts should convince us that S (n) is true
15、for all n i.,2018/9/10,中国石油大学（北京） 董华松,17,Why Induction Is Valid?,The reason comes from the well-ordering property.The Well-Ordering PropertyEvery nonempty set of nonnegative integers has a least element.,2018/9/10,中国石油大学（北京） 董华松,18,Proof,Suppose S (n) were false for one or more of those integers. Th
16、en, by the well-ordering property, there would have to be a smallest value of n, say j, For which S ( j) is false, and yet j=i. Now，j could not be i, because we prove in the basis part that S (i) is true. Thus, j must be greater than i. we know that j 1=i, and S ( j1) is true.,2018/9/10,中国石油大学（北京） 董
17、华松,19,However, we proved in the inductive part that if n i, then S (n) implies S (n + 1). Suppose n j 1. Then we know from the inductive step that S ( j 1) implies S ( j). Since we also know S ( j -1), we can conclude S ( j). We have assumed the negation of which we wanted to prove; that is, assumed S ( j) was false for some j= i. In each case, we derived a contradiction, so S (n) is true or all n=i.,
