Theory of Computation

4.1  THE PDA

Computer science students almost certainly become familiar with the concept of a stack by the time they enroll in a course on the (meta)theory of computation. Let us think of a stack as a string γ, over some alphabet Γ, whose length we are allowed to vary by adding to it or deleting from it exactly one symbol at a time. We have some restrictions to our access to the stack γ:

(1) Adding takes place only at the left end of γ. This end is called the top of the stack. Thus, if A Γ, we can perform a Push operation and go from γ to Aγ. We say that we pushed A into the stack. One often writes γ ↓ A to indicate that we pushed A into γ.

(2) The reverse operation, deleting, is called a Pop operation and it also takes place only at the left end of γ. It is defined only if γ ≠ . Say then γ = Bγ′. Then a pop operation on this γ yields the string γ′. One often writes γ ↑ to indicate that we popped the top of γ (assuming we knew γ ≠ ).

(3) Read access is allowed only at the top of γ.

  (1) We endanger no confusion between the notations γ ↓ and f(a) ↓ as one is about a string (stack) and ...