编译技术编译原理 (9).pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《编译技术编译原理 (9).pdf》由会员分享,可在线阅读,更多相关《编译技术编译原理 (9).pdf(12页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、Finite Automata and Their Decision Problems#Abstract:Finite automata are considered in this paper as instruments for classifying finite tapes.Each one-tape automaton defines a set of tapes,a two-tape automaton defines a set of pairs of tapes,et cetera.The structure of the defined sets is studied.Var
2、ious generalizations of the notion of an automaton are introduced and their relation to the classical automata is determined.Some decision problems concerning automata are shown to be solvable by effective algorithms;others turn out to be unsolvable by algorithms.Introduction Turing machines are wid
3、ely considered to be the abstract prototype of digital computers;workers in the field,how-ever,have felt more and more that the notion of a Turing machine is too general to serve as an accurate model of actual computers.It is well known that even for simple calculations it is impossible to give an a
4、 priori upper bound on the amount of tape a Turing machine will need for any given computation.It is precisely this feature that renders Turings concept unrealistic.In the last few years the idea of a finite automaton has appeared in the literature.These are machines having only a finite number of i
5、nternal states that can be used for memory and computation.The restriction of finite-ness appears to give a better approximation to the idea of a physical machine.Of course,such machines cannot do as much as Turing machines,but the advantage of being able to compute an arbitrary general recursive fu
6、nction is questionable,since very few of these functions come up in practical applications.Many equivalent forms of the idea of finite automata have been published.One of the first of these was the definition of“nerve-nets”given by McCulloch and Pith3 The theory of nerve-nets has been developed by a
7、uthors too numerous to mention.We have been particularly in-fluenced,however,by the work of S.C.Kleene2 who proved an important theorem characterizing the possible action of such devices(this is the notion of“regular event”in Kleenes terminology).J.R.Myhill,in some unpublished work,has given a new t
8、reatment of Kleenes results and this has been the actual point of departure for the investigations presented in this report.We have not,however,adopted Myhills use of directed graphs as*Now at the Department of Mathematics,Hebrew University in+Now at the Department of Mathematics,University of Chica
9、go.$The bulk of this work was done while the authors were associated Jerusalem.114 with the IBM Research Center during the summer of 1957.a method of viewing automata but have retained through-out a machine-like formalism that permits direct com-parison with Turing machines.A neat form of the defini
10、-tion of automata has been used by Burks and Wangl and by E.F.Moore,4 and our point of view is closer to theirs than it is to the formalism of nerve-nets.However,we have adopted an even simpler form of the definition by doing away with a complicated output function and having our machines simply giv
11、e“yes”or “no”answers.This was also used by Myhill,but our generalizations to the “nondeterministic,”“two-way,”and“many-tape”machines seem to be new.In Sections 1-6 the definition of the one-tape,one-way automaton is given and its theory fully developed.These machines are considered as “black boxes”h
12、aving only a finite number of internal states and reacting to their en-vironment in a deterministic fashion.We center our discussions around the application of automata as devices for defining sets of tapes by giving“yes”or“no”answers to individual tapes fed into them.To each automaton there corresp
13、onds the set of those tapes “accepted”by the automaton;such sets will be re-ferred to as definable sets.The structure of these sets of tapes,the various operations which we can perform on these sets,and the relationships between automata and defined sets are the broad topics of this paper.After defi
14、ning and explaining the basic notions we give,continuing work by N e r d e,Myhill,and Shep-herdson,7 an intrinsic mathematical characterization of definable sets.This characterization turns out to be a useful tool for both proving that certain sets are definable by an automaton and for proving that
15、certain other sets are not.In Section 4 we discuss decision problems concerning automata.We consider the three problems of deciding whether an automaton accepts any tapes,whether it ac-IBM JOURNAL APRIL 1959 cepts an infinite number of different tapes,and whether two automata accept precisely the sa
16、me tapes.All three problems are shown to be solvable by effective algo-rithms.In Chapter 1 1 we consider possible generalizations of the notion of an automaton.A nondeterministic automa-ton has,at each stage of its operation,several choices of possible actions.This versatility enables us to construc
17、t very powerful automata using only a small number of internal states.Nondeterministic automata,however,turn out to be equivalent to the usual automata.This fact is utilized for showing quickly that certain sets are defina-ble by automata.Using nondeterministic automata,a previously given constructi
18、on of the direct product of automata(Defini-tion 7),and the mathematical characterization of defina-ble sets,we give short proofs for various well-known closure properties of the class of definable sets(e.g.,the definable sets form a Boolean algebra).Furthermore we include,for the sake of completene
19、ss,a formulation of Kleenes theorem about regular events.In trying to define automata which are closer to the ideal of the Turing machine,while preserving the im-portant feature of using only a preassigned amount of tape,another generalization suggests itself.We relax the condition that the automato
20、n always move in one direc-tion and allow the machine to travel back and forth.In this way we arrive at the idea of a two-way automaton.In Section 7 we consider the problem of comparing one-way with two-way automata,a study that can be con-strued as an investigation into the nature of memory of fini
21、te automata.A one-way machine can be imagined as having simply a keyboard representing the symbols of the alphabet and as having the sequence from the tape fed in by successively punching the keys.Thus no perma-nent record of the tape is required for the operation of the machine.A two-way automaton,
22、&on the other hand,does need a permanent,actual tape on which it can run back and forth in trying to compute the answer.Surpris-ingly enough,it turns out that despite the ability of back-wards reference,two-way automata are no more power-ful than one-way automata.In terms of machine memory this mean
23、s that all information relevant to a computation which an automaton can gather by backward reference can always be handled by a finite memory in a one-way machine.In Chapter 111 we study multitape machines.These automata can read symbols on several different tapes,and we adopt the convention that a
24、machine will read for a while on one tape,then change control and read on another tape,and so on.Thus,with a two-tape machine,a set of pairs of tapes is defined,or we can say a binary relation between tapes is defined.Using again the power-ful tool of nondeterministic automata,we establish a relatio
25、nship between two-tape automata and one-tape automata.Namely,the domain and range of a relation defined by a two-tape automaton are sets of tapes defina-ble by one-tape automata.From this follows the fact that,unlike the sets definable by one-tape automata,the relations definable by two-tape automat
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译技术编译原理 9 编译 技术 原理
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内