编译技术编译原理 (9).pdf

《编译技术编译原理 (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

26、a do not form a Boolean algebra.The problems whether a two-tape au-tomaton accepts any pair of tapes and whether it accepts an infinite number of pairs are shown to be solvable by effective algorithms.We conclude with a brief discussion of two-way,two-tape automata.Here even the problem whether an a

27、u-tomaton accepts any tapes at all is not solvable by an effective algorithm.Furthermore a reduction of two-way automata to one-way automata is not possible.All in all,there is a marked difference between the properties of one-tape automata and those of two-tape automata.The study of the latter is y

28、et far from completion.Chapter 1.One-tape,one-way automata Q 1.The intuitive model and basic definitions An automaton will be considered as a black box of which questions can be asked and from which a“yes”or“no”answer is obtained.The number of questions that can be asked will be infinite,and for sim

29、plicity a question is in-terpreted as any arbitrary finite sequence of symbols from a finite alphabet given in advance.An easy way to imagine the act of asking the question of the automaton is to think of the black box as having the separate sym-bols on a typewriter keyboard.Then the machine is turn

30、ed on and the question is typed in;after an“end of question”button is pressed,a light indicates a“yes”or“no”answer.Other good images of how the automaton could appear physically would use punched cards.Sup-pose that we punch just one symbol or code number for a symbol to a card;then a question is si

31、mply a stack of cards.The automaton is asked a question by having the stack read in a card at a time in the usual way.For the purposes of this paper,we shall not use either of the above images but rather think of the questions as given on one-dimensional tapes.The machine will be endowed with a read

32、ing head which can read one square of the tape (i.e.,one symbol)at a time,and then it can advance the tape one unit and read,say,the next square to the right.We assume the machine stops when it runs out of tape.So much for the external character of an automaton.The internal workings of an automaton

33、will not be analyzed too deeply.We are not concerned with how the machine is built but with what it can do.The definition of the internal structure must be general enough to cover all conceivable machines,but it need not involve itself with problems of circuitry.The simple method of ob-taining gener

34、ality without unnecessary detail is to use the concept of internal states.No matter how many wires or tubes or relays the machine contains,its operation is determined by stable states of the machine at discrete time intervals.An actual existing machine may have billions of such internal states,but t

35、he number is not important from the theoretical standpoint-only the fact that it is finite.As a further simplifying device,we need not consider all the intermediate states that the machine passes IBM JOURNAL*7 15 APRIL 1959 through but only those directly preceding the reading of a symbol.That is,th

36、e machine first reads a symbol or square on the tape,then it may pass through several states before it is ready to read the next symbol.To be able to mimic the action of the automaton,we need not remember all these intermediate states but only the last one it goes into before it reads the next squar

37、e.In fact,if we make a table-of all the transitions from a state and a symbol to a new state,then the whole action of the machine is essentially described.Finally,to get the answer from the machine,we need only distinguish between those states in which the“yes”light is on and those states in which t

38、he “no”light is on when the end of the question is reached.Again,for sim-plicity,it is assumed that all states are in one category or the other but not in both.Thus the whole machine is described when a class of designated states corresponding to the“yes”answers is given.It remains now to give a pre

39、cise mathematical form to these ideas.First a finite alphabet Z is given and fixed for the rest of the discussion.The actual number of symbols in the alphabet is not important.It is only important that all the automata considered use the same alphabet so that different machines can be compared.For i

40、llustration we shall often think of Z as containing only the two symbols 0 and 1.By a tape we shall understand any finite se-quence of symbols from 8.We also include the empty tape with no symbols to be denoted by A.The class of all tapes is denoted by T.If x and y are tapes in T,then xy denotes the

41、 tape obtained by splicing x and y together or by juxtaposing or concatenating the two sequences.In other words,if x=U”U1.u,l-1 and)=TOTI.T,l-l,then X Y=U,U l.U l 1-1 T T 1 .T%-l,where the us and TS are in Z.We assume as obvious the two laws Ax=xA”X,and X(YZ)=(XY 12,for all x,y,z in T.In mathematica

42、l terminology,T to-gether with the operation of juxtaposition forms the free semigroup(with unit)generated by Z.We shall often have occasion to cut tapes into pieces.For example,let x=u,u,.u”l-l;the US are in Z and n is referred to as the length of the tape X.We adopt the following notation kxd=ugu&

43、+1.ut-1,116 where kGlSn.In other words h.l is a section of x run-1BM JOURNAL*APRIL 1959 ning from the(k+1)st symbol of x through the lt”symbol.Clearly,the length of is 1-k.We will agree that if k=l,then k x l=,the tape of length 0.As a useful property of the notation,we have x=Oxl;,x),where k*n,or m

44、ore generally kXrn=kX 1Xnu where k L l f m l n.We shall refer to such tapes as oxk as the initial section or initial portion of x of length k.The obvious notation x”for xxx.x multiplied to-gether n times will also be used with the convention that Having explained all the notations for the tapes that

45、 will be fed into the machines,we turn now to the formal definition of an automaton.Definition 1.A(finite)automaton over the alphabet X is a system$I=(S,M,s,F),where S i s a finite non-empty set(the internal states of s),M is a function de-fined on the Cartesian product SXZ of all pairs of states an

46、d symbols with values in S(the table of transitions or moves of X),so is an element of S(the initial state of ST),and F is a subset of S(the designated final states of 91).Let 81 be an automaton.First of all the function M can be extended from SxZ to SX T in a very natural way by a definition by rec

47、ursion as follows:M(s,A)=x,for s in S;M(s,xu)=M(M(s,x),u),for s in S,x in T,and u i n X.xo=A.The meaning of M(s,x)is very simple:it is that state of the machine obtained by beginning in state s and read-ing through the whole tape x symbol by symbol,chang-ing states according to the given table of mo

48、ves.It should be at once apparent from the definition of the extension of M just given that we have the following useful prop-erty:M(s,xy)=M(M(s,x),y),for all s in S and x,y in T.We may now easily define the set of those tapes which cause the automaton to give a“yes”answer.Definition 2.The set of ta

49、pes accepted or defined by the automaton X,in symbols T(a),is the collection of all tapes x in T such that M(so,x)is in F.Definition 3.The class of all definable sets of tapes,in symbols 3,is the collection of all sets of the form T(%)for some automaton a.The meaning of acceptance can be made cleare

50、r by a diagram.Let x=uo.For each kLn,let Slc=M(So,oXJ t so that for kO we have Sk=M(Sh-l,uk-l).The condition that x be in T(91)is that sn be in F.Each sk is the state of the machine 81 after reaching the kt11 symbol in the tape x.Thus if we write down the fol-lowing diagram:UI)0 1 u2.un-1 S O S1 SZ