《chapter1 形式语言与自动机（研究生）英文课件》由会员分享，可在线阅读，更多相关《chapter1 形式语言与自动机（研究生）英文课件（37页珍藏版）》请在金锄头文库上搜索。
1、形式语言与自动机,学时：36 学分：2 教材： Peter Linz. An Introduction to Formal Languages and Automata . 北京：China Machine Press, 2004 Peter Linz著. 孙家啸译. 形式语言与自动机导论. 北京：机械工业出版社, 2005 最典型的计算机问题求解思路： 问题形式化描述自动化（计算机化）,计算机科学与技术专业的人员应该具有四个基本的专业能力： 计算思维能力（主要包括逻辑思维能力和抽象思维能力） 算法的设计与分析能力 程序设计与实现能力 计算机软硬件系统的认知、分析、设计与应用能力。,参考书目：
2、 王柏,杨娟著. 形式语言与自动机. 北京：北京邮电大学出版社, 2003 Michael Sipser著. 张立昂等译. 计算理论导引. 北京：机械工业出版社, 2000 陈崇昕著. 形式语言与自动机. 北京：北京邮电大学出版社, 1988 John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, Languages and Computation. 北京：清华大学出版社, 2002 Kenneth H Rosen著. 袁崇义,屈婉玲等译.离散数学及其应用. 北京：机械工业出版社,
3、2002 蒋宗礼,姜守旭著. 形式语言与自动机理论. 北京：清华大学出版社, 2003 蒋宗礼著. 形式语言与自动机理论教学参考书. 北京：清华大学出版社, 2003 何成武著.自动机理论及其应用. 北京：科学出版社, 1990 李敏生. 形式语言. 北京：科学出版社, 1989,Formal Languages and Automata,Lin Hong,Chapter 1 INTRODUCTION TO THE THEORY OF COMPUTATION,1.1 Introduction 1.2 Mathematical Preliminaries and Notation 1.3 Thr
4、ee Basic Concepts 1.4 Some Applications,Computer science is a practical discipline. why study theory? （1） theory provides concepts and principles that help us understand the general nature of the discipline. （2） the ideas have some immediate and important applications. （OS、compiler）. （3）The subject
5、matter is intellectually stimulating and fun.,1.1 Mathematical Preliminaries and Notation 1.1.1 sets A set is a collection of elements, without any structure other than membership. the set of integers 0, 1, 2 is shown as S = 0, 1, 2. S = i : i 0, i is even (1.1) “S is set of all i, such that i is gr
6、eater than zero, and i is even,“ The usual set operations are union () ： S1S2=x : xS1 or xS2 intersection () ： S1S2=x : xS1 and xS2 difference () ： S1 S2=x : xS1 and xS2,If , but S contains an element not in S1 we say that S1 is a proper subset of S; we write this as A given set normally has many su
7、bsets. The set of all subsets of a set S is called the powerset of S and is denoted by 2s . Observe that 2s is a set of sets. Example If S is the set a,b,c,then its powerset is 2s = ,a,b,c,a,b,a,c,b,c,a,b,c. Here |S|=3 and | 2s |=8.,Another basic operation is complementation. The complement of a set
8、 S, denoted by, consists of all elements not in S. To make this meaningful, we need to know what the universal set of all possible elements is. If is specified, then =x: x, x S The set with no elements, called the empty set or the null set is denoted by . From the definition of a set, it is obvious
9、that S = S - =S S = The following useful identities, known as the DeMorgans laws, (1.2) (1.3) are needed on several occasions.,1.1.2 Functions and Relations A function is a rule that assigns to elements of one set a unique element of another set. If f denotes a function, then the first set is called
10、 the domain of f, and the second set is its range. f : S1S2 to indicate that the domain of f is a subset of S1 and that the range of f is a subset of S2. If the domain of f is all of S1, we say that f is a total function on S1; otherwise f is said to be a partial function.,Let f(n) and g (n) be func
11、tions whose domain is a subset of the positive integers. If there exists a positive constant c such that for all n , f(n) cg(n) we say that f has order at most g. We write this as f (n) = O (g(n). If |f(n)|c|g(n)|, then f has order at least g,for which we use f(n)= (g(n). Finally, if there exist con
12、stants c1 and c2 such that c1|g(n)| |f(n)| c2|g(n)|,f and g have the same order of magnitude, expressed as f(n)= (g(n).,Example 1.3 Let f (n) = 2n2 + 3n, g (n) = n3, h(n) = 10n2 + 100 Then f (n) = O (g (n), g (n) = (h (n) f (n) = (h (n),Some functions can be represented by a set of pairs (xl,yl),(x2
13、,y2), (x3,y3),., where xi is an element in the domain of the function, and yi is the corresponding value in its range. For such a set to define a function, each xi can occur at most once as the first element of a pair. If this is not satisfied, the set is called a relation. Relations are more genera
14、l than functions: in a function each element of the domain has exactly one associated element in the range; in a relation there may be several such elements in the range. One kind of relation is that of equivalence, a generalization of the concept of equality (identity). To indicate that a pair (x,
15、y) is an equivalence relation, we write xy.,A relation denoted by - is considered an equivalence if it satisfies three rules: the reflexivity rule x x for all x the symmetry rule if x y then y x the transitivity rule if x y and y z, then x z Example: Consider the relation on the set of nonnegative i
16、ntegers defined by x y, if and only if x mod 3 = y mod 3. Then 2 5, 12 0, and 0 36. Clearly this is an equivalence relation, as it satisfies reflexivity, symmetry, and transitivity.,1.1.3 Graphs and Trees Graphs A graph is a construct consisting of two finite sets, the set V = vl, v2, , vn of vertices and
