《形式语言与自动机是计算机科学的基础理论之一.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机是计算机科学的基础理论之一.ppt（90页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Introduction of Formal Language and AutomataINTRODUCTION TO COMPUTATION THEORY1/2/20231中国石油大学（北京）董华松Introduction of Formal Language and AutomataWhy study this course?形式语言与自动机是计算机科学的基础理论之形式语言与自动机是计算机科学的基础理论之一，是计算机学科的专业基础课。一，是计算机学科的专业基础课。在人工智能、电信领域等有广泛的应用。在人工智能、电信领域等有广泛的应用。通通过过一一些些定定理理的的证证明明和和应应用用，对对大
2、大家家进进行行思思维维训训练练，从从而而为为今今后后学学习习通通信信软软件件，协协议议工工程程，编译技术，人工智能等内容提供理论基础。编译技术，人工智能等内容提供理论基础。1/2/20232中国石油大学（北京）董华松Introduction of Formal Language and AutomataCOURSE SUBJECTThis course is an introduction to the Theory of Computation.(有限状态自动机，正规语言，正规表达式,上下文无关文法，上下文无关语言，下推自动机,图灵机，计算问题分类)But what does Theory
3、of Computation mean?1/2/20233中国石油大学（北京）董华松Introduction of Formal Language and AutomataTHEORYvStudy of abstractions of reality.vIrrelevant complications are dropped in order to isolate important concepts.vStudying the theory of subject X means that simplified versions of X are analyzed from various p
4、erspectives.vSo the objects being analyzed in a theory are supposed to be simple.vDoesnt mean that the subject is easy!1/2/20234中国石油大学（北京）董华松Introduction of Formal Language and AutomataCOMPUTATIONTheres more than one kind of computation.Our general approach is to start with very simple,deliberately
5、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 MachinesWe work with each model in order to see what can be done with it.Well reason about the models,e.g.to prove the relationship between them.1
6、/2/20235Introduction of Formal Language and AutomataWHY 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(hence precise)descriptions of
7、computational phenomena.This allow us to use mathematics to solve problems arising from computerIt gives training in argumentation,which is generally useful thing.A questions commonly posed by practised minded students!Here is some answers.1/2/20236中国石油大学（北京）董华松Introduction of Formal Language and Au
8、tomatait 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 for
9、 honing your problem solving skills.You will get much practice in solving problems in this course.1/2/20237中国石油大学（北京）董华松Introduction of Formal Language and AutomataTEXTBOOK1/2/20238中国石油大学（北京）董华松Introduction of Formal Language and AutomataAUTHORS1/2/20239中国石油大学（北京）董华松Introduction of Formal Language a
10、nd AutomataSYLLABIPreliminaries Automata (Finite Automata,Regular expressions,Regular Grammars,Properties of Regular language)Grammars (Context-free Grammars and languages,Pushdown Automata,Properties of Context-free languages)Turing Machines (Introduction to Turing Machines,Computability,Complexity
11、)1/2/202310中国石油大学（北京）董华松Introduction of Formal Language and AutomataPREREQUISITESYou will need a good working knowledge of the material for this course.it is highly recommended that you brush up on the following topics:sets,relations,functions,logic,proof techniques,graph theory,counting techniques,
12、permutations and combinations,etc.1/2/202311中国石油大学（北京）董华松Introduction of Formal Language and AutomataEXAMINATIONvEvery students is required to submit two tractates(30%of total marks)for developing the course.vThe final examination(70%of total marks)will be a two-hour examination at he end of the ter
13、m.vTo pass the course you must have a passing mark on the final examination and the tractates.1/2/202312中国石油大学（北京）董华松Introduction of Formal Language and Automata Session 1v Inductive ProofsvThe Central Concepts of Automata Theory1/2/202313中国石油大学（北京）董华松Introduction of Formal Language and AutomataIndu
14、ctive Proofs1/2/202314中国石油大学（北京）董华松Introduction of Formal Language and AutomataInduction 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 most familiar inductive
15、 proofs deal with integers,but in automate theory,we also need inductive proofs about recursively defined concept as expressions of various sorts.1/2/202315中国石油大学（北京）董华松Introduction of Formal Language and AutomataInduction on IntegersIn order to prove a statement S(n),about an integer n.One common a
16、pproach is to prove two things:v1.The basis step,where we show S(i)for a particular integer i.(Usually,i=0 or i=1.)v2.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 for all n i.1/
17、2/202316中国石油大学（北京）董华松Introduction of Formal Language and AutomataWhy Induction Is Valid?The reason comes from the well-ordering property.The Well-Ordering Property Every nonempty set of nonnegative integers has a least element.1/2/202317中国石油大学（北京）董华松Introduction of Formal Language and AutomataProof
18、Suppose S(n)were false for one or more of those integers.Then,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,
19、and S(j1)is true.1/2/202318中国石油大学（北京）董华松Introduction of Formal Language and Automata 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 t
20、he 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.1/2/202319中国石油大学（北京）董华松Introduction of Formal Language and AutomataThus,we proved our logical reasoning system:The Induction Principle If we prove S(i)
21、and we prove that n i,S(n)implies S(n+1),then we may conclude S(n)for all n=i.1/2/202320中国石油大学（北京）董华松Introduction of Formal Language and AutomataExampleThe harmonic numbers Hk,k=1,2,k，are defined by Use induction principle to prove thatThis inequality can be used to show that the harmonic series is
22、a divergent infinite series.1/2/202321中国石油大学（北京）董华松Introduction of Formal Language and AutomataProof Let S(n)be the proposition that .We need to prove that S(n)is true for n=0,1,2,Basis step:S(0)is true,since H1=1+0/2.Inductive step:Assume that S(n)is true,so that .It must be shown that S(n+1),which
23、 states that ,must also be true under this assumption.n1/2/202322中国石油大学（北京）董华松Introduction of Formal Language and AutomataThis can be done since This establishes the inductive step of the proof.Thus,the inequality for the harmonic numbers is valid for all nonnegative integers n.1/2/202323中国石油大学（北京）董
24、华松Introduction of Formal Language and AutomataQuestionWhat is wrong with the following proof that all horses are the same color?Let S(n)be the proposition that all the horses in a set of n horses are the same color.Basis step:S(1)is true.Inductive step:Assume that S(n)is true,so that all the horses
25、in any set of n horses are the same color.Consider any n+1 horses;number these horses 1,2,n,n+1 are the same color.1/2/202324中国石油大学（北京）董华松Introduction of Formal Language and AutomataConsider any n+1 horses;number these horses 1,2,n,n+1.Now the first n of these horses all must have the same color,and
26、 the last n of these must have the same color.Since the set of the first n horses and the set of the last n horses overlap,all n+1 must be the same color.This shows that S(n+1)is true and finishes the proof by induction.1/2/202325中国石油大学（北京）董华松Introduction of Formal Language and Automata1.Use several
27、 basis cases.i.e.,we prove S(i),S(i+1),S(j)for some j=i2.In proving S(n+1),(n=j)use the truth of all this statement S(i),S(i+1),S(n)rather than just using S(n).3.The conclusion to be made from this basis and inductive step is that S(n)is true for all n=i.Sometimes an induction proof is made by possi
28、ble only by using a more general scheme than the one proposed.Two important generalizations of this scheme are:1/2/202326中国石油大学（北京）董华松Introduction of Formal Language and AutomataExampleShow that if n is an integer greater than 1,the n can be written as the product of primes.Proof Let S(n)be the prop
29、osition that n can be written as the product of primes.Basis step:S(2)is true,since 2 can be written as the product of one prime,itself.Inductive step:Assume that S(k)is true for all positive integers k with 2=k=n.To complete the inductive step,it must shown that S(n+1)is true under this assumption.
30、1/2/202327中国石油大学（北京）董华松Introduction of Formal Language and Automata There are two cases to consider,namely,when n+1 is prime and when n+1 is composite.If n+1 is prime,we immediately see that S(n+1)is true.Otherwise,n+1 is composite and can be written as the product of two positive integers a and b w
31、ith 2=a =b=0:,01,0011,000111,.Example1/2/202361中国石油大学（北京）董华松Introduction of Formal Language and Automata4.The language of strings of 0s and 1s with an equal number of each:,01,10,0011,0101,1001,.5.The language of binary numbers whose value is a prime:10,11,101,111,1011,.1/2/202362中国石油大学（北京）董华松Introd
32、uction of Formal Language and Automata For any alphabet,is a language.,the empty language,is a language over any alphabet.,the language consisting of only the empty string,is also a language over any alphabet.Notice that:1/2/202363中国石油大学（北京）董华松Introduction of Formal Language and Automata It is commo
33、n to describe a language using a set-former:w|something about w.For example,w|w consists of an equal number of 0s and 1s.It is also common to replace w by some expression with parameters and describe the strings in the language by stating conditions on the parameters.For example,and etc.1/2/202364中国
34、石油大学（北京）董华松Introduction of Formal Language and Automata Since languages are sets,the union,intersection,and difference of two languages are immediately defined.Let L and M are both languages,there are other two operations on languages.Concatenation(dot)L.M=w|w=xy,xL,yM Closure(star)where (k=1,2,)The
35、 idea of the closure of a language is somewhat tricky!1/2/202365中国石油大学（北京）董华松Introduction of Formal Language and AutomataL=0,11,L=all strings of 0 s,L=,L=,Question1/2/202366中国石油大学（北京）董华松Introduction of Formal Language and AutomataL.(MN)=L.ML.N Concatenation is left distributive over union.(MN).L=M.L
36、N.L Concatenation is right distributive over union.Closure is idempotent.Is concatenation communicative,i.e.L.M=M.L?Question1/2/202367中国石油大学（北京）董华松Introduction of Formal Language and AutomataGrammars V is a finite set of variables.(非终结符的有限集合非终结符的有限集合)T is a finite set of terminals symbols.(终结符的有限集合终
37、结符的有限集合)P is a finite set of productions of the form xy,where and .(形式为形式为的生成式的有的生成式的有限集合。限集合。)S(V)is a designated variable called the start symbol.(起起始符始符)A grammar is quadruple G=(V,T,P,S).1/2/202368中国石油大学（北京）董华松Introduction of Formal Language and Automata Now we develop the notation for describin
38、g the derivations.Let G=(V,T,P,S)be a grammar ,and xyP.Then we write and say that x derives y.Specially,we have .or,if G is understood1/2/202369中国石油大学（北京）董华松Introduction of Formal Language and Automata We may extend the relationship to present zero,one,or many derivation steps.In other words,we defi
39、ne to be the reflexive and transitive closure of ,as follows:Basis step:Let .Then Inductive step:If ,and ,then .Use induction we can prove that if and ,then 1/2/202370中国石油大学（北京）董华松Introduction of Formal Language and AutomataLet G(V,T,P,S)be a grammar.Then the set If wL(G),then the sequence is a deri
40、vation of the sentence w.The strings S,w1,wn,which contain variables as well as terminals,are called sentential forms of the derivation.In general,we call the language of variable A if AV.is the language generated by G.1/2/202371中国石油大学（北京）董华松Introduction of Formal Language and Automata Consider the
41、grammar G=(S,a,b,P,S),with P given by S aSb,S.The string aabb is a sentence in the language generated by G.A grammar G completely defines L(G),but it may not be easy to get a very explicit description of the language from the grammar.Here,however,the answer is fairly clear.it is not hard to conjectu
42、re that ,and it is easy to prove it.Example1/2/202372中国石油大学（北京）董华松Introduction of Formal Language and AutomataChomskyChomsky文法体系分类文法体系分类G(V,T,P,S)G(V,T,P,S)属于属于ChomskyChomsky文法体系文法体系该体系对生成式的形式做了一些规定，分为四类，该体系对生成式的形式做了一些规定，分为四类，即即0 0型、型、1 1型、型、2 2型、型、3 3型文法型文法0 0型文法：无限制文法型文法：无限制文法 对应的语言：递归可枚举语言，与图灵机等价
43、。对应的语言：递归可枚举语言，与图灵机等价。1/2/202373中国石油大学（北京）董华松Introduction of Formal Language and Automata1 1型文法型文法 也称上下文有关文法（也称上下文有关文法（CSGCSG：Context-Context-sensitive Grammar),sensitive Grammar),生成式的形式为生成式的形式为，其中其中|，对应的语言：上下文有关语言（对应的语言：上下文有关语言（CSLCSL：Context-Context-sensitive Language)sensitive Language)若不考虑若不考虑，与
44、线性有界自动机（与线性有界自动机（LBA,Linear LBA,Linear Bounded AutomatonBounded Automaton）等价。等价。1/2/202374中国石油大学（北京）董华松Introduction of Formal Language and Automata2 2型文法型文法 也称上下文无关文法（也称上下文无关文法（CFGCFG：Context-free Context-free Grammar)Grammar)AA,AV,AV,且且 对应的语言：上下文无关语言（对应的语言：上下文无关语言（CFLCFL：Context-free Language)Conte
45、xt-free Language)。对应的自动机：下推自动机（对应的自动机：下推自动机（PDA:PushdownPDA:Pushdown Automaton)Automaton)。1/2/202375中国石油大学（北京）董华松Introduction of Formal Language and Automata3 3型文法型文法也称正则文法也称正则文法右线性文法（右线性文法（Right-linear GrammarRight-linear Grammar）：）：ABAB 或或 AA A A、BN,TBN,T*。左线性文法（左线性文法（Left-linear GrammarLeft-linea
46、r Grammar）：）：ABAB或或 AA A A、BN,BN,TT*。对应的语言：正则语言对应的语言：正则语言对应的自动机：有限自动机（对应的自动机：有限自动机（Finite Finite AutomatonAutomaton）。）。1/2/202376中国石油大学（北京）董华松Introduction of Formal Language and AutomataExampleG=(A,B,C,a,b,d,P,A)P:AAB；ABCAAB；Ad；Ba；Cb 是是1型文法。型文法。A=dA=AB=dB=daA=AB=ABB=dBB=daB=daaA=AB=CAAB=bAAB=bdAB=bd
47、CAAB=bdbAAB=bdbdAB=bdbddB=bdbdda1/2/202377中国石油大学（北京）董华松Introduction of Formal Language and AutomataG=(A,B,C,a,b,c,P,A)P:Aabc AaBbc BbbB BcCbcc bCCb aCaaB aCaa 是是1型文法。型文法。其定义的其定义的 L=anbncn|n1 A=abc A=aBbc=abBc=abCbcc=aCbbcc=aabbcc =aaBbbccExample1/2/202378中国石油大学（北京）董华松Introduction of Formal Language
48、and AutomataExampleG=(S,B,C,a,b,P,A)P:SaC；SbB；BaS；BbBB Ba；CbS；CaCC；Cb 是是2型文法型文法 S=aC=ab S=aC=aaCCS=aC=abS=abaC=ababS=ababaC=abababS=bB=bbBB=bbaSB=bbaaCB=bbaabB=bbaaba1/2/202379中国石油大学（北京）董华松Introduction of Formal Language and AutomataExampleG=(A,B,C,G=(A,B,C,a,b,ca,b,c,P,A),P,A)P:P:ABaABa；AcAc；BCbBCb
49、；CcCc左线性文法左线性文法 L=c,L=c,cbacba 正则语言正则语言注意：已知语言求文法，文法不是唯一的，即可注意：已知语言求文法，文法不是唯一的，即可以有不同的表达方法以有不同的表达方法。1/2/202380中国石油大学（北京）董华松Introduction of Formal Language and Automata四类文法之间的关系四类文法之间的关系 只是对生成式形式加以限制只是对生成式形式加以限制0 0型型 无限制无限制1 1型型 不允许不允许AA形式形式2 2型型3 3型型 属于属于2 2型型 不含不含AA的的2 2型、型、3 3型属于型属于1 1型，型，1 1型、型、2
50、 2型、型、3 3型均属于型均属于0 0型。型。1/2/202381中国石油大学（北京）董华松Introduction of Formal Language and AutomataAutomata An automaton is an abstract model of a digital computer having discrete input and output.(具有离散输入输出的数学模型。具有离散输入输出的数学模型。)Following figure shows a schematic representation of a general automaton.1/2/2023