Ti: The tape symbols of Mi are all pairs of symbols from Г2, that is, Г2 x Г2. The input symbols of Mi are those pairs with an input symbol of M2 in the first component and a blank in the second component, that is, pairs of the form [a,B], where a is in S. The blank of Mi has blanks in both components. Additionally, for every symbol X in Г2, there is a pair [X, *] in Г1. Here, * is a new symbol, not in Г2, and serves to mark the left end of Mis tape.

5i: The transitions of Mi are as follows:

1- 1(90, [o, B]) = {qi,[a, *], R), for any a in S. The first move of Mi puts the * marker in the lower track of the leftmost cell. The state becomes qi, and the head moves right, because it cannot move left or remain stationary.

2. 5iiqi,[X,B]) = ([q2,U],[X,B],L), for any X in Г2. In state qx, Mi establishes the initial conditions of M2, by returning the head to its initial position and changing the state to [521 i-e., the initial state of M2, with attention focused on the upper track of Mi-

3. If S2{q,X) = (p,Y,D), then for every Z in Г2:

(a) 6x{[q,UUX,Z]) = i\p,U],[Y,Z],D) and

(b) 5i{[q,L],[Z,X]) = i\p,L],[Z,Y],D),

where D is the direction opposite D, that is, L if Z) - Й and R if D = L. К Ml is not at its leftmost cell, then it simulates M2 on the appropriate track - the upper track if the second component of state is и and the lower track if the second component is L. Note, however, that when working on the lower track, M2 moves in the direction opposite that of M2. That choice makes sense, because the left half of M2s tape has been folded, in reverse, along the lower track of Mis tape.

4. lfS2iq,X} = {p,Y,R),then

6i{[q, L], [X, *]) 6i{[q, UUX, *]) - ([p, U], [Y, *],R)

This rule covers one case of how the left endmarker * is handled. If M2 moves right from its initicd position, then regardless of whether it had previously been to the left or the right of that position (as reflected in the fact that the second component of Mis state could be L or f7), -Ml must move right and focus on the upper track. That is. Ml will next be at the position represented by Xi in Fig. 8.19.

5. li62{q,X) = ip,Y,L), then

5i {[q, L], [X, *]) = 5i {{q, U], [X, .]) = ([p, Ц, [У, *], Л)

This rule is similar to the previous, but covers the case where M2 moves left from its initied position. Mi must move right ftom its

endmarker, but now focuses on the lower track, i.e., the cell indicated by X-i in Fig. 8.19.

Ft: The accepting states Fi are those states in F2 x {U,L}, that is all states of Ml whose first component is an accepting state of M2. The attention of Ml may be focused on either the upper or lower track at the time it accepts.

The proof of the theorem is now essentially complete. We may observe by induction on the number of moves made by M-2 that Mi will mimic the ID of M-2 on its own tape, if you take the lower track, reverse it, and follow it by the upper track. Also, we note that Mi enters one of its accepting states exactly when My does. Thus, L(Mi) = ЦМ2). □

8.5.2 Multistack Machines

We now consider several computing models that are based on generalizations of the pushdown automaton. First, we consider what happens when we give the PDA several stacks. We already know, from Example 8.7, that a Turing machine can accept languages that are not accepted by any PDA with one stack. It turns out that if we give the PDA two stacks, then it can accept any language that a TM can accept.

We shall then consider a class of machines called counter machines. These machines have only the ability to store a finite number of integers ( counters ), and to make different moves depending on which if any of the counters are currently 0. The counter machine can only add or subtract one from the counter, and cannot toll two different nonzero counts from each other. In effect, a counter is like a stack on which we can place only two symbols: a bottom-of-stack marker that appears only at the bottom, and one other symbol that may be pushed and popped from the stack.

Input

Accept/reject

S?JRh

Figure 8.20: A machine with three stacks

We shall not give a formal treatment of the multistack machine, but the idea is suggested by Fig. 8.20, A fc-stack machine is a deterministic PDA with к stacks. It obtains its input, like the PDA does, from an input source, rather than having the input placed on a tape or stack, as the TM does. The multistack macliine has a finite control, which is in one of a finite set of states. It has a finite stack alphabet, which it uses for all its stacks. A move of the multistack machine is based on:

1. The state of the finite control.

2. The input symbol read, which is chosen from the finite input alphabet. Alternatively, the multistack machine can make a move using e input, but to make the machine deterministic, there cannot be a choice of an e-move or a non-e-move in any situation.

3. The top stack symbol on each of its stacks. In one move, the multistack machine can:

a) Change to a new state.

b) Replace the top symbol of each stack with a string of zero or more stack symbols. There can be (and usually is) a different replacement string for each stack.

Thus, a typical transition rule for a fc-stack machine looks like: 6{q,a,Xi,X2,...,Xk) - (р,71Л2,-..,7л)

The interpretation of this rule is that in state q, with X; on top of the ith stack, for i = 1,2, the machine may consume a (either an input symbol or e)

from its input, go to state p, and replace X, on top of the ith stack by string 7i, for each i = 1,2, ...,k. The multistack machine accepts by entering a final state.

We add one capability that simplifies input processing by this deterministic machine: we assume there is a special symbol $, called the endmarker, that appears only at the end of the input and is not part of that input. The presence of the endmarker allows us to know when we have consumed all the available input. We shall see in the next theorem how the endmarker makes it easy for the multistack machine to simulate a Turing machine. Notice that the conventional TM needs no special endmarker, because the first blank serves to mark the end of the input.

Theorem 8.13; If a language L is accepted by a Turing machine, then L is accepted by a two-stack machine.