1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 47
Текст из файла (страница 47)
To be precise, let M d , the deterministic version of M, be a device withthe same set of states as M, but with two tapes. The first tape is the tape of M,initially containing the input w, while the second tape initially contains a stringof n integers in the range 1, ... ,r, say it i2 ... in. Md then operates as follows forn steps: In the first step, among the r possible next state-action combinations(PI, btl, ... , (Pr, br ) that are applicable to the initial configuration, Md choosesthe i 1 t h -that is, (pi), bi ) ), the one suggested by the currently scanned symbolin the second tape, i}.
Md also moves its second tape head to the right, so thatit next scans i 2 . In the next step, Md takes the i 2 th combination, then the i3th,and so on. When Md sees a blank on its second tape, meaning that it has runout of "hints," it halts.Md is an important ingredient in our design of the deterministic Turingmachine M' that simulates M. We shall describe M' as a 3-tape Turing machine;we know by Theorem 4.3.1 that M' can be converted into an equivalent singletape Turing machine. The three tapes of M' are used as follows:(1) The first tape is never changed; it always contains the original input w,so that each simulated computation of M can begin afresh with the sameinput.(2) The second and the third tapes are used to simulate the computations ofAId, the deterministic version of M, with all strings in {1,2, ...
,r}*. Theinput is copied from the first tape onto the second before M' begins tosimulate each new computation. Initially, the third tape contains e, theempty string (and therefore the simulation of Md will not even start thefirst time around).Chapter 4: TURING MACHINES226(3) Between two simulations of Md, M' uses a Turing machine N to generatethe lexicogmphically next string in {I, 2, ... , r} *. That is, N will generatefrom e the strings 1,2, ... , r, 11, 12, ...
, rr, 111, .... For r = 2, N is preciselythe Turing machine that computes the binary successor function (Example4.2.3); its generalization to r > 2 is rather straightforward.M' is is the Turing machine given in Figure 4-22. By Cl-+2 we mean asimple Turing machine that erases the second tape and copies the first tape onthe second. B3 is the machine that generates the lexicographically next stringin the third tape.
Finally, M;,3 is the deterministic version of M, operating orttapes 2 and 3. This completes the description of M'.Figure 4-22We claim that M' halts on an input w if and only if (some computation of)M does. Suppose that M' indeed halts on input w; by inspecting Figure 4-22,this means that Md halts with its third tape head not scanning a blank. Thisimplies that, for some string i 1 i2 ... in E {I, 2, ... , r} *, M d , when started withw on its first tape and i 1i2 ...
in on its second, halts before reaching the blankpart of its second tape. This, however, means that there is a computation ofM on input w that halts. Conversely, if there is a halting computation of Mon input w, say with n steps, then M', after at most r + r2 + ... + rn failedattempts, the string in {I, 2, ... , r}' corresponding to the choices of M's haltingcomputation will be generated by B3, and Md will halt scanning the last symbolof this string. Thus M' will halt, and the proof is complete .•As we had expected, the simulation of a nondeterministic Turing machine bya deterministic one is not a step-by-step simulation, as were all other simulationswe have seen in this chapter. Instead, it goes through all possible computationsof the nondeterministic Turing machine.
As a result, it requires exponentiallymany steps in n to simulate a computation of n steps by the nondeterministic'machine -whereas all other simulations described in this chapter are in factpolynomial. Whether this long and indirect simulation is an intrinsic feature ofnondeterminism, or an artifact of our poor understanding of it, is a deep andimportant open question, explored in Chapters 6 and 7 of this book.Problems for Section 4.55.1. Give (in abbreviated notation) nondeterministic 1\lring machines that accept these languages.2274.6: Grammars(a) a*abb*baa*(b) {wwRuu R : w,U E {a,by}4.5.2.
Let M =(K,~,15, s, {h}) be the following nondeterministic Turing machine:K ={qo,ql,h},~={ a, t>, U},s =qo,6. ={ (qO, U, ql, a), (qo, U, ql, U), (ql, U, ql, U), (ql, a, qo, ~), (ql, a, h, ~)}Describe all possible computations of five steps or less by M starting fromthe configuration (qo, t>U). Explain in words what M does when startedfrom this configuration. What is the number r (in the proof of Theorem4.5.1) for this machine?4.5.3. Although nondeterministic Turing machines are not helpful in showing closure under complement of the recursive languages, they are very convenientfor showing other closure properties. Use nondeterministic Turing machinesto show that the class of recursive languages is closed under union, concatenation, and Kleene star.
Repeat for the class of recursively enumerablelanguages.BGRAMMARSIn this chapter we have introduced several computational devices, namely theTuring machine and its many extensions, and we have demonstrated that theyare all equivalent in computational power. All these various species of Turingmachines can be reasonably called automata, like their weaker relatives -the finite automata and the pushdown automata- studied in previous chapters.
Likethose automata, Turing machines and their extensions act basically as languageacceptors, receiving an input, examining it, and expressing in various ways theirapproval or disapproval of it. Two important families of languages, the recursiveand the recursively enumerable languages, have resulted.But in previous chapters we have seen that there is another important family of devices, very different in spirit from language acceptors, that can be used todefine interesting classes of languages: language genemtors, such as regular expressions and context-free grammars.
In fact, we have demonstrated that thesetwo formalisms provide valuable alternative characterizations of the classes oflanguages defined by language acceptors. This chapter would not be completewithout such a maneuver: We shall now introduce a new kind oflanguage generator that is a generalization ofthe the context-free grammar, called the grammar228Chapter 4: TURING MACHINES(or unrestricted grammar, to contrast it with the context-free grammars) andshow that the class of languages generated by such grammars is precisely theclass of recursively enumerable ones.Let us recall the essential features of a context-free grammar. It has analphabet, V, which is divided into two parts, the set of terminal symbols, ~,and the set of nonterminal symbols, V -~.
It also has a finite set of rules, eachof the form A -+ u, where A is a nonterminal symbol and u E V*. A contextfree grammar operates by starting from the start symbol S, a nonterminal, andrepeatedly replacing the left-hand side of a rule by the corresponding right-handside until no further such replacements can be made.In a grammar all the same conventions apply, except that the left-hand sidesof rules need not consist of single nonterminals. Instead, the left-hand side ofa rule may consist of any string of terminals and nonterminals containing atleast one nonterminal.
A single step in a derivation entails removing the entiresubstring on the left-hand side of a rule and replacing it by the correspondingright-hand side. The final product is, as in context-free grammars, a stringcontaining terminals only.Definition 4.6.1: A grammar (or unrestricted grammar, or a rewritingsystem) is a quadruple G = (V,~, R, S), whereV is an alphabet;~ ~ V is the set of terminal symbols, and V - ~ is called the set ofnonterminal symbols;S E V - ~ is the start symbol; andR, the set of rules, is a finite subset of (V*(V - ~)V*) x V*.We write u -+ v if (u, v) E R; we write u '*c v if and only if, for someWI, W2 E V* and some rule u' -+ v' E R, u = WI U ' W2 and v = WI v' W2.
As usual,'*c is the reflexive, transitive closure of '*c. A string W E ~* is generated byG if and only if S '*c w; and L(G), the language generated by G is the setof all strings in ~* generated by G.We also use other terminology introduced originally for context-free grammars; for example, a derivation is a sequence of the form Wo '*c WI '*c... '*c W n ·Example 4.6.1: Any context-free grammar is a grammar; in fact, a context-freegrammar is a grammar such that the left-hand side of each rule is a member ofV -~, rather than V*(V -~)V*.
Thus, in a grammar, a rule might have the formuAv -+ uwv, which could be read "replace A by W in the context of u and v."Of course, the rules of a grammar may be of a form even more general than this;but it turns out that any language that can be generated by a grammar can begenerated by one in which all rules are of this "context-dependent replacement"type (Problem 4.6.3).02294.6: GrammarsExample 4.6.2: The following grammar G generates the language {afibficfin 2': I}. G = (V,~, R, S), whereV = {S,a,b,c,A,B,C,Ta,Tb,Tc},~ = {a, b, c}, andR = {S -+ ABCS,S -+ Tc,CA -+ AC,BA -+ AB,CB -+ BC,CTc -+ Tcc,CTc -+ TbC,BTb -+ Tbb,Bn -+ Tab,ATa -+ Taa,Ta -+ e}.The first three rules generate a string of the form (ABC)nTc.
Then the nextthree rules allow the A's, B's, and C's in the string to "sort out" themselvescorrectly, so that the string becomes AnB"cnTc. Finally, the remaining rulesallow the Tc to "migrate" to the left, transforming all C's to c's, and thenbecoming n. In turn, Tb migrates to the left, transforming all B's into b's andbecoming T a , and finally Ta transforms all A's into a's and then is erased.It is rather obvious that any string of the form anbfic n can be produced thisway. Of course, many more strings that contain nonterminals can be produced;however, it is not hard to see that the only way to erase all nonterminals is tofollow the procedure outlined above. Thus, the only strings in {a, b, c} that canbe generated by G are those in {anbfic n : n 2': 1}.oEvidently, the class of languages generated by grammars contains certainnon-context-free specimens.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
