O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

5.1   ADDING A SECOND STACK; TURING MACHINES

We introduced the PDA as a special case (albeit nondeterministic) of the URM, with a single number-type read/write variable—the stack variable. Actually, we viewed this variable as a string-type variable suppressing a detailed look into how a URM can effect string operations such as “pop” and “push”, until now. As in Section 2.11, we can identify strings over a finite alphabet of m symbols with natural numbers—the latter written in notation base-(m + 1). The correct way to do this (cf. 2.11.0.32, III) is to fix an order of the alphabet and identify its members {a1, a2, . . . ,am} with the “digits” 1, 2, ... , m (i.e., ai with i). Thus a non-empty string

Images

is uniquely represented by (and represents) the number

jr(m + 1)r + jr−1(m + 1)r−1 + ... j1(m + 1) + j0

0 corresponds to the string ∊.

Assume now that the stack variable is x, and that its contents is the string γ, which, in detail, is the string in (1). Moreover, let us have the stack top located at the right end of γ rather than the left end.

Pause. Why is this not an about face of any significance vis à vis our earlier conventions?Images

Then we can do a pop—and assign the popped symbol in the variable z, if we wish—as follows

The stack (contents) change corresponds to the effect of

Both ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required