[Math] Question regarding stack operation notation in PDA

automatacomputer science

I'm currently reading two books:

  1. An Introduction to Formal Languages and Automata, 4th Edition by Peter Linz.
  2. Introduction to the Theory of Computation, 2nd Edition by Michael Sipser.

What confused me is the notations are used in these two books are very different from each other. For example,

Let $L = \{a^nb^{2n} : n \geq 0\}$

The solution to this PDA is straightforward:

  • If we read an $a$, push two markers (or stack symbol) onto the stack.
  • If we read a $b$, pop one marker (or stack symbol) out of the stack.

Now, let's draw the actual PDA:

  1. Peter Linz's solution:
    enter image description here
  2. Michael Sipser's solution:
    enter image description here

There are several differences that I've noticed:

  • With Peter Linz's stack mechanism, we can actually push 2 symbols onto the stack at a time as opposed to Michael Sipser's one, we can only push 1 symbol onto the stack at a time.
  • Peter Linz's solution also takes the top of the stack into account each time it performs a push. For example, the transition from $q_0$ to $q_1$:
    $$a, z \rightarrow 11z$$
    $$a, 1 \rightarrow 111$$
    Here, the PDA pushes two 1's onto a stack each time it reads an $a$, but it also looks at what symbol is currently on the top of the stack. The string $11z$ for instance means top $\rightarrow$ bottom and is read from left to right. While Micheal Sipser's solution doesn't really care about the top stack symbol. As long as it reads an $a$, it pushes a $x$ onto the stack. More specifically, the notation
    $$a, b \rightarrow c$$ means
  • read a, if $a = \lambda$, read nothing.
  • pop b, if $b = \lambda$, pop nothing.
  • push c, if $c = \lambda$, push nothing.

I personally prefer Michael Sipser's notation over Peter Linz's one because I think it's not necessary to keep track of which symbol is currently on the stack. Unless there is a case when this extra step matters, otherwise I feel it's quite trivial to express the transition function in Michael Sipser's way. Besides, I wonder if "is it correct" to allow pushing "2" symbols at a time onto stack? Plus, among these two methods, which one is more standard and more widely used?

Update
Correct PDA of Peter Linz's solution:
enter image description here

Best Answer

I think the main moral here should be it does not matter.

The two methods are evidently equivalent - pushing any given finite number of symbols at one time can be accomplished using a finite set of dedicated states. In general when discussing models of computation one must not lose itself in specific details of implementation as long as there is no serious difference between them (one example for such a difference: the number of states in a NDFA for a language can be exponentially smaller than the number of states in the best DFA for the language).

When you'll reach computability theory you'll see that this "freedom from specific implementation details" is truly crucial if you want to keep focusing on the important matters.

This is not a feature of theoretical computer science alone, of course; many mathematics books on diverse subjects use notation that can be quite different from one another. There is no universal rule as to what is correct; you should choose the notation you like best and stick to it.

Related Question