1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 55
Текст из файла (страница 55)
If no Ai symbol was pushed, or more than one, then M3 can accept-the input is in L 4. Otherwise, M4 compares its stack contents (a string of theform y~ Aiyf when read from the top down) with the part of the input up to thenext :::}. If a mismatch is found before Ai is encountered, or if it is discoveredthat Ai is not replaced in the input by (3f (a string remembered by M4 in itsstate space), or if a mismatch is found after this, or if the next:::} (or the end ofthe input) is not found immediately after the stack becomes empty, then againM4 accepts.
Otherwise it rejects.This concludes the description of 1\[4, and it is clear that L(M4) = L 4 • Theconstruction for L5 is very similar. We can thus design context-free grammarsthat generate each of the languages L1 through L 5 ; hence we can design acontext-free grammar G 2 for their union.Thus, given any generalized grammar G 1 , we can construct a context-freegrammar G 2 such that L(G 2 ) = DG~. But we know that DG~ = ~* if and onlyif L(G 1 ) = 0. We conclude that if we had an algorithm for deciding whether anygiven context-free grammar generates all of ~*, then we could use this algorithmfor deciding whether a given generalized grammar generates the empty language,which we know is impossible.
The proof of Part (a) is complete.(b) If we could tell whether two context-free grammars generate the same language, then we would be able to tell if a context-free grammar generates ~*:take the second grammar to be a trivial grammar that does generate ~*.(c) If we could tell whether any two pushdown automata are equivalent, thenwe would be able to tell if two given context-free grammars are equivalent bytransforming them into two pushdown automata that accept the same language,and then testing them for equivalence.(d) If there were an algorithm for minimizing the number of states of a pushdownautomaton, just as there is for finite automata, then we would be able to tell ifa given pushdown automaton accepts ~*: It does if and only if the optimizedpushdown automaton has one state and accepts ~*.
And it is decidable whethera one-state pushdown automaton accepts ~* (this is established in Problem5.5.1) .•Problems for Section 5.55.5.1. Show that it is decidable, given a pushdown automaton M with one state,whether L(M) = ~*. (Hint: Show that such an automaton accepts allstrings if and only if it accepts all strings of length one.)5.5.2. A Post correspondence system is a finite set P of ordered pairs ofnonempty strings; that is, P is a finite subset of ~* x ~*. A match of P262Chapter 5: UNDECIDABILITYis any string w E ~.
such that, for some n > 0 and some (not necessarilydistinct) pairs (111, VI), (112, V2), ... , (ll n .V n ), W = 111112 .. ·ll n = VI V2 ... V n ·(a) Show that it is undecidable, given a Post correspondence system, to determine whether it has a match. (Start with a restricted version, in whichmatches must start with a distinguished pair in P.)(b) Use (a) above to find an alternative proof of Theorem 5.5.2.5.5.3. A (nondeterministic) 2-head finite automaton (THFA) consists of a finitecontrol, an input tape, and two heads that can read but not write on thetape and move only left to right. The machine is started in its initial statewith both heads on the leftmost square of the tape. Each transition is ofthe form (q,a,b,p), where q and p are states, and a and b are symbols ore.
This transition means that M may, when in state q, read a with its firsthead and b with its second and enter state p. M accepts an input string bymoving both heads together off the right end of the tape while entering adesignated final state.(a) Show that it is solvable, given a THFA M and an input string w, whetherM accepts w.(b) Show that it is unsolvable, given a THFA M, whether there is any stringthat M accepts. (Use the previous problem.)BAN UNSOLVABLE TILING PROBLEMWe are given a finite set of tiles, each one unit square. We are asked to tile thefirst quadrant of the plane with copies of these tiles, as shown in Figure 5-1.
Wehave an infinite supply of copies of each tile.Figure 5-1The only restrictions are that a special tile, the origin tile, must be placedin the lower left-hand corner; that only certain pairs of tiles may abut each other5.6: An Unsolvable Tiling Problem263horizontally; and that only certain pairs of tiles may abut each other vertically.(Tiles may not be rotated or turned over.) Is there an algorithm for determiningwhether the first quadrant can be tiled, given a finite set of tiles, the origin tile,and the adjacency rules?This prohlem can be formalized as follows.
A tiling system is a quadrupleD = (D, do, H, V), where D is a finite set of tiles, do ED, and H, V C;;; D x D.A tiling by D is a function f : N x N ..-+ D such that the following hold:f(O,O) = do,(f(m, n), f(m + 1, n)) E H for all m,n E N,(f(m, n), f(m, n + 1)) E V for all m,n E N.Theorem 5.6.1: The problem of determining, given a tiling system, whetherthere is a tiling by that system is undecidable.Proof: We reduce to this tiling problem the problem of determining, given aTuring machine M, whether M fails to halt on input e. This is simply thecomplement of the halting problem, and thus an undecidable problem.
If thisproblem can be reduced to the tiling problem, the tiling problem is surely undecidable.The basic idea is to construct from any Turing machine M a tiling systemD such that a tiling by D, if one exists, represents an infinite computation hy .Mstarting from the blank tape. Configurations of M are represented horizontallyin a tiling; successive configurations appear one above the next. That is, thehorizontal dimension represents the tape of M, while the vertical dimensionstands for time. If M never halts on the empty input, successive rows can betiled ad infinitum; but if M halts after k steps, it is impossible to tile more thank rows.In constructing the relations H and V, it is helpful to think of the edges ofthe tiles as being marked with certain information; we allow tiles to abut eachother horizontally or vertically only if the markings on the adjacent edges areidentical. On the horizontal edges, these markings are either a symbol from thealphabet of M or a state-symbol combination.
The tiling system is arranged sothat if a tiling is possible, then by looking at the markings on the horizontal edgesbetween the nth and (n + l)st rows of tiles, we can read off the configurationof M after n - 1 steps of its computation. Thus only one edge along such aborder is marked with a state-symbol pair; the other edges are marked withsingle symbols.The marking on a vertical edge of a tile is either absent (it only matchesvertical edges also with no marking) or consists of a state of M, together witha "directional" indicator, which we indicate by an arrowhead.
(Two exceptions264Chapter 5: UNDECIDABILITYare given under (e) below.) These markings on the vertical edges are used tocommunicate a left- or right-hand movement of the head from one tile to thenext.To be specific, let M = (K, y:" 0, s, H). Then V = (D, do, H, V), where Dcontains the following tiles:(a) For each a E y:, and q E K, the tiles illustrated in Figure 5-2, whichsimply communicate any unchanged symbols upwards from configuration to configuration.aDaFigure 5-2(b) For each a E y:, and q E K such that O(q, a)= (p, b), where p E KandbEy:" the tile shown in Figure 5-3.
This tile communicates the head positionupwards and also changes the state and scanned symbol appropriately.(p,b)D(q,a)Figure 5-3(c) For each a E y:, and q E K such that O(q, a) = (p, -+) for some p E K, andfor each bEy:, - {t>} ,the tiles shown in Figure 5-4. These tiles communicate headmovement one square from left to right, while changing the state appropriately.Notice that, naturally enough, we allow no state to enter the left-end symbol t>from the left.a(p, b)(q,a)EJbFigure 5-45.6: An Unsolvable Tiling Problem265(d) Tiles similar to those of (c) for the case in which 6 (q, a) = (p, +-) areillustrated in Figure 5-5. The symbol I> is not excepted here.a(p,b)[j(q,a)bFigure 5-5These tiles do the bulk of the simulation of M by V.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
