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 {*a*_{1}, *a*_{2}, . . . ,*a*_{m}} with the “digits” 1, 2, ... , *m* (i.e., *a*_{i} with *i*). Thus a non-empty string

is uniquely *represented* by (and *represents*) the number

*j _{r}*(

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?

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 ...

Start Free Trial

No credit card required