1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 48
Текст из файла (страница 48)
But precisely how large is this class of languages?More importantly, how does it relate to the other two important extensions of thecontext-free languages we have seen in this chapter, namely, the recursive and therecursively enumerable languages? As it happens, grammars play with respectto Turing machines precisely the same role that context-free grammars play inrelation to pushdown automata, and regular expressions to finite automata:Theorem 4.6.1: A language is generated by a grammar if and only if it isrecursively enumerable.230Chapter 4: TURING MACHINESProof: Only if. Let G = (V,~, R, S) be a grammar.
We shall design a Turingmachine M that semidccides the language generated by G. In fact, M will benondeterministic; its conversion to a deterministic machine that semidecides thesame language is guaranteed by Theorem 4.5.l.M has three tapes. The first tape contains the input, call it w, and isnever changed.
In the second tape, M tries to reconstruct a derivation of Wfrom S in the grammar G; M therefore starts by writing S on the second tape.Then M proceeds in steps, corresponding to the steps of the derivation beingconstructed. Each step starts with a nondeterministic transition, guessing onebetween IRI + 1 possible states. Each of the first IRI of these IRI + 1 states is thebeginning of a sequence of transitions that applies the corresponding rule to thecurrent contents of the second tape. Suppose that the chosen rule is u -+ v.
Mthen scans its second tape from left to right, nondeterministically stopping atsome symbol. It then checks that the next lui symbols match u, erases u, shiftsthe rest of the string appropriately to make just enough space for v, and writes vin u's place. If the check fails, M enters an unending computation -the presentattempt at generating W has failed.The IRI + 1st choice of M entails checking whether the current string equalsw, the input. If so, M halts and accepts: w can indeed be generated by G. Andif the strings are found unequal, M again loops forever.It is clear that the only possible halting computations of M are those thatcorrespond to a derivation of win G.
Thus M accepts w if and only if wE L(G),and the only if direction has been proved.If. Suppose now that M = (K,~, 15, s, {h}) is a Turing machine. It will beconvenient to assume that ~ and K are disjoint, and that neither contains thenew endmarker symbol <1. We also assume that M, if it halts, it always does soin the configuration (h, C>U) -that is, after having erased its tape. Any Turingmachine that semidecides a language can be transformed into an equivalentone that satisfies the above conditions.
We shall construct a grammar G =(V, ~ - {U, C>}, R, S) that generates the language L ~ (~ - {u, C>})* semidecidedbyM.The alphabet V consists of all symbols in ~ and all states in K, plus thestart symbol S and the endmarker <1. Intuitively, the derivations of G will simulate backward computations of M. We shall simulate configuration (q, c>uQw)by the string c>uaqW<1 -that is, by the tape contents, with the current state inserted immediately after the currently scanned symbol, and with the endmarker<1 appended at the end of the string.
The rules of G simulate backwards moves ofM. That is, for each q E K and a E ~, G has these rules, depending on b(q, a).(1) If b(q, a) = (p, b) for some p E K and b E ~, then G has a rule bp -+ aq.(2) If b(q, a) = (p, -+) for some p E K, then G has a rule abp -+ aqb for allb E ~, and also the rule aU p<1 -+ aq<1 (the last rule reverses the extension2314.6: Grammarsof the tape to the right by a new blank).(3) If b(q, a) = (p, f-) for some p E K, and a -:j:. U, then G has a rule pa -+ aq.(4) If b(q, U) = (p, f-) for some p E K, then G has a rule pab -+ aqb for allb E ~, and also the rule p<J -+ Uq<J that reverses the erasing of extraneousblanks.Finally, G contains certain transitions for the beginning of the computation(the end of the derivation) and the end of the computation (the beginning of thederivation).
The ruleS -+ I> U h<Jforces the derivation to start exactly where an accepting computation would end.The other rules are I> U s -+ e, erasing the part of the final string to the left ofthe input, and <J -+ e, erasing the endmarker and leaving the input string.The following result makes precise our notion that G simulates backwardcomputations of M:Claim: For any two configurations (ql, Ul al wd and (q2, U2a2w2) of M, we havethat (ql,Ul~wd f-M (q2,U2a2w2) if and only ifu2a2q2w2<J '*G ulalqlWl<J·The proof of the claim is a straightforward case analysis on the nature of themove M, and is left as an exercise.We now complete the proof of the theorem, by showing that, for all w E(~ - {I>, u})*, M halts on w if and only if wE L(G). wE L(G) if and only ifbecause S -+ I> U h<J is the only rule that involves S, and the rules I> U s -+ eand <J -+ e are the only rules that allow for the eventual erasing of the stateand the endmarker <J.
Now, by the claim, I> U h<JI> U sW<J if and only if(s,l>h!w) f-M (h,I>!J), which happens if and only if M halts on w. This completesthe proof of the Theorem .•'*cTheorem 4.6.1 identifies grammars with an aspect of the Turing machinesthat we have deemed unrealistic -semidecision, with its one-sided definitionthat provides no information when the input is not in the language. This isconsistent with what we know about grammars: If a string can be generated bythe grammar, we can patiently search all possible derivations, starting from theshorter ones and proceeding to the longer ones, until we find the correct one.But if no derivation exists, this process will go on indefinitely, without giving usany useful information.As it turns out, we can also identify grammars with the more useful modesof computation based on Turing machines.232Chapter 4: TURING MACHINESDefinition 4.6.2: Let G = (V,~, R, S) be a grammar, and let f : ~.
H ~. bea function. We say that G computes f if, for all w, v E ~*, the following istrue:SwS =*0 v if and only if v = f(w).That is, the string consisting of the input w, with a starting symbol of G oneach side, yields exactly one string in ~': the correct value of f(w).A function f : ~* H ~. is called grammatically computable if and onlyif there is a grammar G that computes it.We leave the proof of the following result -a modification of the proof ofTheorem 4.6.1- as an exercise, see Problem 4.6.4:Theorem 4.6.2: A function f :grammatically computable.~*H~.is recursive if and only if it isProblems for Section 4.64.6.1.
(a) Give a derivation of the string aaabbbccc in the grammar of Example4.6.2.(b) Prove carefully that the grammar in Example 4.6.2 generates the language L = {anbnc n : n ;::: I}.4.6.2. Find grammars that generate the following languages:(a) {ww: w E {a,b}'}(b) {a 2 " : n ;::: O}(c) {an' : n ;::: O}4.6.3. Show that any grammar can be converted into an equivalent grammar withrules of the form uAv -+ uwv, with A E V -~, and u, v, wE V*.4.6.4. Prove Theorem 4.6.2. (For the only if direction, given a grammar G, showhow to construct a Turing machine which, on input w, outputs a stringU E ~* such that SwS =*0 u, if such a string u exists.
For the if direction,use a simulation similar to the proof of Theorem 4.6.1, except in the opposite(forward) direction.)4.6.5. An oddity in the use of grammars to compute functions is that the order inwhich rules are applied is indeterminate. In the following alternative, dueto A. A. Markov (1903~1979), this indeterminacy is avoided. A Markovsystem is a quadruple G = (V,~, R, Rd, where V is an alphabet; ~ <:;;; V;R is a finite sequence (not set) of rules (UI -+ VI, ... ,Uk -+ Vk), whereUi, Vi E V*; and RI is a set of rules from R. The relation w =*c w' isdefined as follows: If there is an i such that Ui is a substring of w, then let4.7: Numerical Functions233i be the smallest such number, and let WI be the shortest string such that= WIUiW2; then W :::}c w' provided that w' = WIViW2.
Thus if a ruleis applicable, then there is at most one rule, and it is applicable in exactlyone position. We say that G computes a function f : ~. H ~* if for allWU E~'U= Uo :::}c UI-+c ... :::}cUn-I :::}C Un= f(u),and the first time that a rule from RI was used was the last one, Un-I :::}CShow that a function is computable by a Markov system if and only ifit is recursive. (The proof is similar to that of Theorem 4.6.2.)Un.BNUMERICAL FUNCTIONSLet us now adopt a completely different point of view on computation, one thatis not based on any explicit computational or information-processing formalismsuch as Turing machines or grammars, but instead focuses on what has to becomputed: functions from numbers to numbers.
For example, it is clear that thevalue of the functionf(m, n)= m· n 2 + 3· m 2 .m+l7can be computed for any given values of m and n, because it is the composition offunctions -addition, multiplication, and exponentiation, plus a few constantsthat can be computed. And how do we know that exponentiation can be computed? Because it is recursively defined in terms of a simpler function (namely,multiplication) and values at smaller arguments.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
